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
| void dfs(int u, int fa) {
sz[u] = 1;
for (auto v : G[u]) {
if (v == fa) {
continue;
}
dfs(v, u);
}
dp[u][0][0] = 1;
for (auto v : G[u]) {
if (v == fa) {
continue;
}
memcpy(tmp, dp[u], sizeof(dp[u]));
memset(dp[u], 0, sizeof(dp[u]));
for (int i = 0; i <= sz[u] / 2; i++) {
for (int j = 0; j <= sz[v] / 2; j++) {
if (!dp[v][j][0]) {
continue;
}
if (tmp[i][0]) {
add_mod(dp[u][i + j][0], 1ll * tmp[i][0] * dp[v][j][0] % Mod);
}
if (tmp[i][0]) {
add_mod(dp[u][i + j + 1][1], 1ll * tmp[i][0] * dp[v][j][0] % Mod);
}
if (tmp[i][1]) {
add_mod(dp[u][i + j][1], 1ll * tmp[i][1] * dp[v][j][0] % Mod);
}
}
for (int j = 0; j <= sz[v] / 2; j++) {
if (!dp[v][j][1]) {
continue;
}
if (tmp[i][1]) {
add_mod(dp[u][i + j][1], 1ll * tmp[i][1] * dp[v][j][1] % Mod);
}
if (tmp[i][0]) {
add_mod(dp[u][i + j][0], 1ll * tmp[i][0] * dp[v][j][1] % Mod);
}
}
}
sz[u] += sz[v];
}
}
int main() {
cin >> n;
for (int i = 1; i <= 2 * n - 1; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
fac[0] = 1;
for (int i = 1; i <= 2 * n; i++) {
fac[i] = 1ll * fac[i - 1] * i % Mod;
}
invf[2 * n] = inv(fac[2 * n]);
for (int i = 2 * n - 1; i >= 0; i--) {
invf[i] = 1ll * invf[i + 1] * (i + 1) % Mod;
}
f[0] = 1;
for (int i = 2; i <= 2 * n; i += 2) {
f[i] = 1ll * fac[i] * inv(ksm(2ll, i / 2)) % Mod * invf[i / 2] % Mod;
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
g[i] = 1ll * (dp[1][i][0] + dp[1][i][1]) * f[2 * (n - i)] % Mod;
}
int ans = f[2 * n];
for (int i = 1; i <= n; i++) {
int add = g[i];
if (i & 1) {
add = Mod - add;
}
ans = (ans + add) % Mod;
}
printf("%d\n", ans);
return 0;
}
|
