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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5005;
const int MAXM = 305;
const ll MOD = 998244353;
struct Edge {
int v, nxt;
}edge[MAXN << 1];
int head[MAXN], cnt;
inline void AddEdge(int u, int v) {
edge[++cnt].v = v;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
int n, m;
ll f[MAXN][MAXN][3], t[MAXN][MAXN][3];
int size[MAXN];
void dp(int u, int fa) {
size[u] = 1;
f[u][1][0] = 1;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].v;
if (v == fa) continue;
dp(v, u);
for (int i = 1; i <= size[u]; ++i) {
for (int j = 1; j <= size[v]; ++j) {
ll tmp1 = (f[v][j][0] + f[v][j][1] * 2 + f[v][j][2] * 2) % MOD;
ll tmp2 = (f[v][j][0] + f[v][j][1]) % MOD;
t[u][i + j][0] = (t[u][i + j][0] + tmp1 * f[u][i][0]) % MOD;
t[u][i + j][1] = (t[u][i + j][1] + tmp1 * f[u][i][1]) % MOD;
t[u][i + j][2] = (t[u][i + j][2] + tmp1 * f[u][i][2]) % MOD;
t[u][i + j - 1][1] = (t[u][i + j - 1][1] + tmp2 * f[u][i][0]) % MOD;
t[u][i + j - 1][2] = (t[u][i + j - 1][2] + tmp2 * f[u][i][1]) % MOD;
}
}
size[u] += size[v];
for (int i = 1; i <= size[u]; ++i) {
f[u][i][0] = t[u][i][0],
f[u][i][1] = t[u][i][1],
f[u][i][2] = t[u][i][2],
t[u][i][0] = t[u][i][1] = t[u][i][2] = 0;
}
}
}
ll inv[MAXN], fac[MAXN], facinv[MAXN];
inline ll C(int n, int m) {
return fac[n] * facinv[m] % MOD * facinv[n - m] % MOD;
}
ll a[MAXN * MAXM], c[MAXN * MAXM], b[MAXN];
int len;
int main() {
fac[0] = facinv[0] = 1;
inv[1] = fac[1] = facinv[1] = 1;
for (int i = 2; i <= 5000; ++i) {
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
fac[i] = fac[i - 1] * 1ll * i % MOD;
facinv[i] = facinv[i - 1] * inv[i] % MOD;
}
a[0] = 1;
scanf("%d", &m);
for (int cas = 1; cas <= m; ++cas) {
cnt = 0;
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
int u, v;
scanf("%d%d", &u, &v);
AddEdge(u, v), AddEdge(v, u);
}
dp(1, 0);
for (int i = 1; i <= n; ++i) {
ll tmp = (f[1][i][0] + f[1][i][1] * 2 + f[1][i][2] * 2) * fac[i] % MOD;
for (int j = 1; j <= i; ++j) {
b[j] = (b[j] + ((i - j) & 1 ? -1 : 1) * tmp * C(i - 1, j - 1) % MOD * facinv[j] % MOD) % MOD;
}
}
for (int i = 0; i <= len; ++i) c[i] = 0;
for (int i = 0; i <= len; ++i)
for (int j = 1; j <= n; ++j)
c[i + j] = (c[i + j] + a[i] * b[j] % MOD) % MOD;
len += n;
for (int i = 0; i <= len; ++i) a[i] = c[i];
for (int i = 0; i <= n; ++i) {
head[i] = 0;
b[i] = 0;
for (int j = 0; j <= n; ++j) {
f[i][j][0] = f[i][j][1] = f[i][j][2] = 0;
t[i][j][0] = t[i][j][1] = t[i][j][2] = 0;
}
}
}
ll ans = 0;
for (int i = 0; i <= len; ++i)
ans = (ans + a[i] * fac[i] % MOD * inv[i] % MOD + MOD) % MOD;
printf("%lld", ans);
return 0;
}
|