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
100
101
102
103
104
105
106
| #include <cstdio>
#include <set>
#include <vector>
#define pb push_back
#include <algorithm>
using namespace std;
template <class Type>
void read (Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0';
flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
x < 0 && (putchar('-'), x = ~x + 1);
x > 9 && (write(x / 10), 0);
putchar('0' + x % 10);
}
typedef long long LL;
const int N = 1e5 + 10;
const int base = 31, ibase = 128805723, mod = 998244353;
void adj (int &x) { x += x >> 31 & mod; }
int pbase[N];
int binpow (int b, int k = mod - 2)
{
int res = 1;
for (; k; k >>= 1, b = (LL)b * b % mod)
if (k & 1) res = (LL)res * b % mod;
return res;
}
struct Tree
{
int n, p[N], sz[N], f[N], g[N];
vector <int> e[N], h[N], s[N];
void input ()
{
for (int i = 1, a, b; i < n; ++i)
{
read(a, b);
e[a].pb(b), e[b].pb(a);
}
}
int calc (int u)
{
s[u].resize(h[u].size());
sort(h[u].begin(), h[u].end());
int res = 0;
for (int i = 0; i < h[u].size(); ++i)
{
int k = (LL)h[u][i] * pbase[i] % mod;
adj(res += k - mod);
adj((s[u][i] = k) += (i ? s[u][i - 1] : 0) - mod);
}
return (res + 1ll) * sz[u] % mod;
}
void dfs1 (int u)
{
sz[u] = 1;
for (int v : e[u]) if (v ^ p[u])
{
p[v] = u;
dfs1(v);
sz[u] += sz[v];
h[u].pb(f[v]);
}
f[u] = calc(u);
}
void dfs2 (int u)
{
g[u] = calc(u);
for (int v : e[u]) if (v ^ p[u])
{
int t = lower_bound(h[u].begin(), h[u].end(), f[v]) - h[u].begin();
sz[u] -= sz[v], sz[v] += sz[u];
int k = ((t ? s[u][t - 1] : 0) + (LL)(s[u][h[u].size() - 1] - s[u][t]) * ibase + 1) % mod * sz[u] % mod;
adj(k), h[v].pb(k);
dfs2(v);
sz[v] -= sz[u], sz[u] += sz[v];
}
}
void init () { dfs1(2), dfs2(2); }
} A, B;
int main ()
{
pbase[0] = 1;
for (int i = 1; i < N; ++i)
pbase[i] = (LL)pbase[i - 1] * base % mod;
int n; read(n); A.n = n, B.n = n + 1;
A.input(), B.input();
A.init(), B.init();
set <int> s;
for (int i = 1; i <= n; ++i) s.insert(A.g[i]);
for (int i = 1; i <= n + 1; ++i)
if (B.e[i].size() == 1 && s.count(((LL)B.g[i] * binpow(n + 1) - 1) % mod))
return write(i), 0;
return 0;
}
|