Description
Link：QOJ 14324
给出一个包含 n 个点的树。
你可以进行若干次操作，每次你可以删除这棵树的一个叶子（即保证剩下部分仍然是连通的）。
你需要求出有多少种删除叶子的方案，使得剩下部分的重心唯一（这里的重心定义与平常相同，即最大子树最小的节点）。
答案对 998244353 取模，两个方案不同当且仅当删除叶子节点构成的集合不同。
数据范围：1≤n≤3×103。
时空限制：3s / 1024MiB。
Solution
一棵树至多有两棵重心。
若一棵树有两个重心，则这两个重心相邻，并且整棵树可以被相连的这条边，划分成大小相等的两支。
有了这个结论就好算了。使用总的连通块个数，减去包含两个重心的连通块个数即可。
总的连通块个数
假定以 1 为根。设 f(u) 表示在 u 的子树内，包含点 u 的连通块个数，则有
f(u)=v∈son(u)∏(f(v)+1)
最后总的连通块个数即为 ∑i=1nf(i)。
包含两个重心的连通块个数
由先前的结论，相当于是要找出有多少个，两个大小相同并且相连的连通块。
记相连的边为关键边。这两个连通块在树上的位置关系一定是一上一下，并且由关键边相连。我们不妨把下面部分的节点权值设成 −1，把上面部分的节点权值设成 −1。那么两个部分大小相同，等价于权值和为 0。
考虑 dp。设 f(u,i,0/1) 表示在 u 的子树内，包含点 u 的连通块大小为 i，是否存在关键边的方案数。当合并两棵子树 u,v 时，有转移
f′(u,i+j,0)←+f(u,i,0)×f(v,j,0)f′(u,i+j,1)←+f(u,i,1)×f(v,j,0)f′(u,i+j,1)←+f(u,i,0)×f(v,j,1)f′(u,i−j,1)←+f(u,i,0)×f(v,j,0)
当然这里的 i,j 分别只需要枚举到 [−szeu,szeu] 与 [−szev,szev] 即可，时间复杂度 O(n2)。
换根树上背包的时间复杂度是 O(n3) 的。
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
| #include <bits/stdc++.h>
using s64 = long long;
template <class T>
inline void chmin(T &x, const T &y) {
if (x > y) {
x = y;
}
}
template <class T>
inline void chmax(T &x, const T &y) {
if (x < y) {
x = y;
}
}
const int mod = 998244353;
void add(int &x, const int &y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
void dec(int &x, const int &y) {
x -= y;
if (x < 0) {
x += mod;
}
}
const int N = 3010;
int n;
struct Graph {
std::vector< std::vector<int> > table;
void init(int _n) {
table.assign(_n + 1, {});
}
void add_edge(int u, int v) {
table[u].push_back(v);
}
} G;
int ans;
int sze[N];
namespace p1 {
int f[N];
void dp(int u, int fu) {
f[u] = 1;
for (int v : G.table[u]) {
if (v == fu) continue;
dp(v, u);
f[u] = 1ll * f[u] * (f[v] + 1) % mod;
}
add(ans, f[u]);
}
}
namespace p2 {
int f[N][N * 2][2], tmp[N * 2][2];
void dp(int u, int fu) {
sze[u] = 1;
f[u][0 + n][0] = 0, f[u][1 + n][0] = 1, f[u][-1 + n][0] = 0;
f[u][0 + n][1] = 0, f[u][1 + n][1] = 0, f[u][-1 + n][1] = 0;
for (int v : G.table[u]) {
if (v == fu) continue;
dp(v, u);
int t = sze[u] + sze[v];
for (int i = -t; i <= t; i ++) {
tmp[i + n][0] = 0;
tmp[i + n][1] = 0;
}
for (int i = -sze[u]; i <= sze[u]; i ++) {
add(tmp[i + n][0], f[u][i + n][0]);
add(tmp[i + n][1], f[u][i + n][1]);
for (int j = -sze[v]; j <= sze[v]; j ++) {
add(tmp[i + j + n][0], 1ll * f[u][i + n][0] * f[v][j + n][0] % mod);
add(tmp[i + j + n][1], 1ll * f[u][i + n][1] * f[v][j + n][0] % mod);
add(tmp[i + j + n][1], 1ll * f[u][i + n][0] * f[v][j + n][1] % mod);
add(tmp[i - j + n][1], 1ll * f[u][i + n][0] * f[v][j + n][0] % mod);
}
}
for (int i = -t; i <= t; i ++) {
f[u][i + n][0] = tmp[i + n][0];
f[u][i + n][1] = tmp[i + n][1];
}
sze[u] = t;
}
dec(ans, f[u][0 + n][1]);
}
}
void work() {
std::cin >> n;
G.init(n);
for (int i = 1; i < n; i ++) {
int x, y;
std::cin >> x >> y;
G.add_edge(x, y), G.add_edge(y, x);
}
ans = 0;
p1::dp(1, 0);
p2::dp(1, 0);
std::cout << ans << '\n';
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T;
std::cin >> T;
while (T --) {
work();
}
return 0;
}
|