結果
問題 | No.912 赤黒木 |
ユーザー |
![]() |
提出日時 | 2019-10-18 22:49:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 380 ms / 3,000 ms |
コード長 | 2,786 bytes |
コンパイル時間 | 2,957 ms |
コンパイル使用メモリ | 202,644 KB |
最終ジャッジ日時 | 2025-01-07 23:26:18 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
//#pragma GCC optimize("Ofast")//#pragma GCC target("avx")//#undef LOCAL#include <bits/stdc++.h>using namespace std;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }template <class T> using V = vector<T>;template <class T> using VV = V<V<T>>;#ifdef LOCALstruct PrettyOS {ostream& os;bool first;template <class T> auto operator<<(T&& x) {if (!first) os << ", ";first = false;os << x;return *this;}};template <class... T> void dbg0(T&&... t) {(PrettyOS{cerr, true} << ... << t);}#define dbg(...) \do { \cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \dbg0(__VA_ARGS__); \cerr << endl; \} while (false);#else#define dbg(...)#endiftemplate <class T, class U>ostream& operator<<(ostream& os, const pair<T, U>& p) {return os << "P(" << p.first << ", " << p.second << ")";}template <class T> ostream& operator<<(ostream& os, const V<T>& v) {os << "[";for (auto d : v) os << d << ", ";return os << "]";}VV<int> g;V<int> dif, odd, sz;void dfs(int p, int b) {for (int d: g[p]) {if (d == b) continue;dfs(d, p);sz[p] ^= sz[d];}}int ma = 0;int dfs2(int p, int b) {V<int> top;top.push_back(-TEN(8));top.push_back(-TEN(8));if (odd[p]) top.push_back(dif[p]);for (int d: g[p]) {if (d == b) continue;dif[d] = dif[p];if (sz[d]) dif[d]++;else dif[d]--;top.push_back(dfs2(d, p));}sort(top.begin(), top.end(), greater<ll>());ma = max(ma, top[0] + top[1] - 2 * dif[p]);return top[0];}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(20);int n;cin >> n;g = VV<int>(n);for (int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b; a--; b--;g[a].push_back(b);g[b].push_back(a);}V<int> deg(n);for (int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b; a--; b--;deg[a] = 1 - deg[a];deg[b] = 1 - deg[b];}odd = V<int>(n);sz = V<int>(n);for (int i = 0; i < n; i++) {if (deg[i] % 2) {odd[i] = sz[i] = 1;}}dfs(0, -1);dbg(odd, sz);assert(sz[0] == 0);int ans = n - 1;for (int i = 0; i < n; i++) {if (sz[i]) ans++;}dif = V<int>(n);dfs2(0, -1);dbg(ans, ma);cout << ans - ma << endl;return 0;}