結果
問題 |
No.912 赤黒木
|
ユーザー |
![]() |
提出日時 | 2019-10-19 02:02:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 300 ms / 3,000 ms |
コード長 | 3,074 bytes |
コンパイル時間 | 1,520 ms |
コンパイル使用メモリ | 124,356 KB |
最終ジャッジ日時 | 2025-01-07 23:57:37 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <chrono> #define _USE_MATH_DEFINES #include <cmath> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <iomanip> #include <iterator> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <utility> #include <vector> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() const int INF = 0x3f3f3f3f; const long long LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(10); } } iosetup; /*-------------------------------------------------*/ vector<int> graph[200000]; int subtree[200000] = {}, dp[200000][3] = {}; bool odd[200000] = {}; void dfs1(int par, int ver) { if (odd[ver]) subtree[ver] = 1; for (int e : graph[ver]) if (e != par) { dfs1(ver, e); subtree[ver] += subtree[e]; } } void dfs2(int par, int ver) { for (int e : graph[ver]) { if (e != par) dfs2(ver, e); } dp[ver][0] = 0; for (int e : graph[ver]) if (e != par) { dp[ver][0] += dp[e][0]; if (subtree[e] & 1) ++dp[ver][0]; } if (subtree[ver] >= 1) { int mn = INF; for (int e : graph[ver]) if (e != par) { int zero = dp[e][0] + (subtree[e] & 1); int one = dp[e][1] + (subtree[e] % 2 == 0); mn = min(mn, one - zero); } dp[ver][1] = min(dp[ver][1], dp[ver][0] + mn); if (odd[ver]) dp[ver][1] = min(dp[ver][1], dp[ver][0]); if (subtree[ver] >= 2) { int mn2 = INF; for (int e : graph[ver]) if (e != par) { int zero = dp[e][0] + (subtree[e] & 1); int two = dp[e][2] + (subtree[e] & 1); mn2 = min(mn2, two - zero); } dp[ver][2] = min(dp[ver][2], dp[ver][0] + mn2); vector<int> mn1; for (int e : graph[ver]) if (e != par) { int zero = dp[e][0] + (subtree[e] & 1); int one = dp[e][1] + (subtree[e] % 2 == 0); mn1.emplace_back(one - zero); } if (mn1.size() >= 2) { sort(ALL(mn1)); int mnmn = mn1[0] + mn1[1]; dp[ver][2] = min(dp[ver][2], dp[ver][0] + mnmn); } if (odd[ver]) dp[ver][2] = min(dp[ver][2], dp[ver][0] + mn); } } } int main() { memset(dp, INF, sizeof(dp)); int n; cin >> n; REP(_, n - 1) { int a, b; cin >> a >> b; --a; --b; graph[a].emplace_back(b); graph[b].emplace_back(a); } REP(_, n - 1) { int c, d; cin >> c >> d; --c; --d; odd[c] = !odd[c]; odd[d] = !odd[d]; } dfs1(-1, 0); dfs2(-1, 0); cout << n - 1 + min(dp[0][0], dp[0][2]) << '\n'; return 0; }