1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
| #include<bits/stdc++.h> using namespace std; typedef unsigned long long ull;
const int maxn = 100005; const ull seed = 1000000007;
ull H[maxn], H2[maxn]; ull size[maxn];
vector<int> G1[maxn], G2[maxn]; map<ull, bool> mp;
int N, R; int ans = maxn;
void dfs1(int u, int fa) { H[u] = size[u] = 1; for (vector<int>::iterator it = G1[u].begin(); it != G1[u].end(); it++) { int v = *it; if (v == fa) continue; dfs1(v, u); size[u] += size[v]; H[u] ^= (H[v] * seed + size[v]); } }
void dfs2(int u, int fa) { if (u != R) { H2[u] = H[u] ^ ((H2[fa] ^ (H[u] * seed + size[u])) * seed + ((ull)N - size[u])); } else H2[u] = H[u]; for (vector<int>::iterator it = G1[u].begin(); it != G1[u].end(); it++) { int v = *it; if (v == fa) continue; dfs2(v, u); } }
void dfs3(int u, int fa) { H[u] = size[u] = 1; for (vector<int>::iterator it = G2[u].begin(); it != G2[u].end(); it++) { int v = *it; if (v == fa) continue; dfs3(v, u); size[u] += size[v]; H[u] ^= (H[v] * seed + size[v]); } }
void dfs4(int u, int fa) { if (u != R) { H2[u] = H[u] ^ ((H2[fa] ^ (H[u] * seed + size[u])) * seed + ((ull)N + 1 - size[u])); } else H2[u] = H[u]; for (vector<int>::iterator it = G2[u].begin(); it != G2[u].end(); it++) { int v = *it; if (v == fa) continue; dfs4(v, u); } }
int main() { scanf("%d", &N); for (register int i = 1; i < N; ++i) { int u, v; scanf("%d%d", &u, &v); G1[u].push_back(v); G1[v].push_back(u); } R = 1; dfs1(1, 0); dfs2(1, 0); for (register int i = 1; i <= N; ++i) { int u, v; scanf("%d%d", &u, &v); G2[u].push_back(v); G2[v].push_back(u); } for (register int i = 1; i <= N; ++i) mp[H2[i]] = 1; R = 2; dfs3(2, 0); dfs4(2, 0); for (register int i = 1; i <= 1; ++i) { if ((int)G2[i].size() == 1) { ull w = H2[G2[i][0]] ^ (H[i] * seed + 1); if (mp[w]) return printf("%d", i), 0; } } R = 1; dfs3(1, 0); dfs4(1, 0); for (register int i = 2; i <= N + 1; ++i) { if ((int)G2[i].size() == 1) { ull w = H2[G2[i][0]] ^ (H[i] * seed + 1); if (mp[w]) return printf("%d", i), 0; } } return 0; }
|