题解：P4582 [FJOI2014] 树的重心
Pengzt
·
·
题解
树的重心
题目链接。cnblogs。luogu。
Problem
有 T（T \le 50）组测试数据。
每次给出 n（\le 200）个节点的树，求它的连通子图数量，使得它的重心与整棵树的重心重合。答案对质数 P 取模。
Sol
不妨设 d_i 表示以 u 为根的时候，i 的子树大小。
先找到树的重心。发现只有 \max d_i = \frac n2 的时候才会出现两个重心。
不妨记这个重心为 rt，
令 f_{u, i} 表示 u 子树中，连通子图大小为 i 的数量。
有转移：f'_{u, i} = \sum\limits_{j = 0}^{sz_v} f_{u, i - j}\cdot f_{v, j}。然后 f\gets f'。
当 $u$ 为根的时候，记连通块大小为 $sz$，那么要统计 $\max d_i < \frac{sz}2$ 的答案，这个东西其实不是很好统计，但是发现 $\ge \frac{sz}2$ 的儿子很少，考虑统计 $\max d_i > \frac{sz - 1}2$ 的数量。令 $g_{v, i}$ 表示不考虑 $v$ 这个儿子和 $u$，连通块大小为 $i$ 的方案数。则答案为 $\sum \limits_{i = 1}^{sz_v} f_{v, i} \cdot \sum \limits_{j = 0}^{i - 1} g_{v, j}$。然后就是求出 $g_{u, i}$。不难发现 $g$ 可以表示为一个前缀和后缀的并，这个前后缀的预处理是可以 $\mathcal{O}(n\cdot\sum sz_v) = \mathcal{O}(n^2)$ 的。直接暴力合并出 $g$ 的话是 $\mathcal{O}(n^3 / n^2\log)$ 的，但是发现 $g$ 只有前 $sz_v$ 项有用，所以合并就变为 $\mathcal{O}(\sum sz_v^2) = \mathcal{O}(n^2)$ 的了。
+ 两个重心：
把 $(rt_1, rt_2)$ 断开，然后分别以 $rt_1$，$rt_2$ 为根跑一遍。然后答案为 $\sum f_{rt_1, i}\cdot f_{rt_2, i}$。
时间复杂度 $\mathcal{O}(n^2)$。
具体实现可以参考代码，感觉已经很清楚了。
#### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
mt19937_64 eng(time(0) ^ clock());
template <typename T>
T rnd(T l, T r) { return eng() % (r - l + 1) + l; }
const int P = 10007;
int n, rt1, rt2;
vector<int> e[205];
int sz[205], mx[205];
void DFS(int u, int ff) {
sz[u] = 1;
for (int v : e[u])
if (v != ff) {
DFS(v, u);
sz[u] += sz[v];
mx[u] = max(mx[u], sz[v]);
}
mx[u] = max(mx[u], n - sz[u]);
if (!rt1 || mx[u] < mx[rt1])
rt1 = u, rt2 = 0;
else if (mx[u] == mx[rt1])
rt2 = u;
}
int f[205][205], g[205][205], pre[205][205], suf[205][205], temp[205];
void Work(int u, int ff) {
sz[u] = 1;
int son = 0;
f[u][0] = 1;
for (int v : e[u])
if (v != ff) {
++son;
Work(v, u);
memset(temp, 0, sizeof (temp));
sz[u] += sz[v];
for (int i = 0; i <= sz[u]; i++)
for (int j = 0; j <= min(sz[v], i); j++)
(temp[i] += f[u][i - j] * f[v][j]) %= P;
memcpy(f[u], temp, sizeof (f[u]));
}
for (int i = sz[u]; i; --i) f[u][i] = f[u][i - 1];
f[u][0] = 1;
if (!son) f[u][1] = 1;
}
int ans;
void Solve(int test) {
memset(f, 0, sizeof (f)), memset(g, 0, sizeof (g)), memset(pre, 0, sizeof (pre)), memset(suf, 0, sizeof (suf)), memset(mx, 0, sizeof (mx));
rt1 = rt2 = 0;
scanf("%d", &n);
for (int i = 1, u, v; i < n; i++)
scanf("%d%d", &u, &v), e[u].emplace_back(v), e[v].emplace_back(u);
DFS(1, 0);
if (rt2) {
Work(rt1, rt2);
Work(rt2, rt1);
ans = 0;
for (int i = 1; i <= n / 2; i++)
(ans += f[rt1][i] * f[rt2][i]) %= P;
printf("Case %d: %d\n", test, ans);
for (int i = 1; i <= n; i++) e[i].clear();
return;
}
ans = 1;
Work(rt1, 0);
for (int i : e[rt1]) {
int s = 0;
for (int j = 0; j <= n; j++)
(s += f[i][j]) %= P;
(ans *= s) %= P;
}
pre[0][0] = 1;
int len = (int)e[rt1].size();
for (int i = 0; i < len; i++) {
int v = e[rt1][i];
for (int j = 0; j <= n; j++)
for (int k = 0; k <= min(sz[v], j); k++)
(pre[i + 1][j] += pre[i][j - k] * f[v][k]) %= P;
}
suf[len + 1][0] = 1;
for (int i = len - 1; i >= 0; --i) {
int v = e[rt1][i];
for (int j = 0; j <= n; j++)
for (int k = 0; k <= min(sz[v], j); k++)
(suf[i + 1][j] += suf[i + 2][j - k] * f[v][k]) %= P;
}
for (int i = 1; i <= len; i++) {
int v = e[rt1][i - 1];
for (int j = 0; j <= sz[v]; j++)
for (int k = 0; k <= j; k++)
(g[i][j] += pre[i - 1][j - k] * suf[i + 1][k]) %= P;
for (int j = 1; j <= sz[v]; j++)
(g[i][j] += g[i][j - 1]) %= P;
for (int j = 1; j <= sz[v]; j++)
(ans -= f[v][j] * g[i][j - 1]) %= P;
}
(ans += P) %= P;
printf("Case %d: %d\n", test, ans);
for (int i = 1; i <= n; i++) e[i].clear();
}
int main() {
int T;
scanf("%d", &T);
for (int i = 1; i <= T; i++)
Solve(i);
return 0;
}
```