首先找出原树的重心。
考虑重心的性质，有：以其为根的重构树中，每一个子树大小都不超过 $\frac{n}{2}$，那么其为重心。
又重心有一个或者两个，可以分类讨论。
两个重心
由于这两个重心相邻，所以可以切断它们之间的连边，形成两棵树。
设：$f(i,j)$ 表示以 $i$ 为根的子树中，包含 $i$ 且有 $j$ 个节点的连通块个数，可以树形背包在 $O(n^2)$ 的时间内计算。
最后答案为 $\sum_{i=1}^{\min(sz[u],sz[v])} f(u,i) \cdot f(v,i)$，其中 $u$，$v$ 表示两个重心。
一个重心
在以该重心为根求出 $f$ 的基础上，考虑使用总方案数 $\sum_{i=1}^n f(u,i)$（其中 $u$ 为重心），减去其一个子树大小大于 $\frac{i}{2}$（或等于，因为这会创造一个新的重心）的方案数。
注意到如果一个子树大小大于等于 $\frac{i}{2}$ 那么这样的子树仅有一个，可以直接枚举。
现在我们枚举了一个子树，所以在 $f(u,i)$ 中我们要退掉其的贡献，记其为 $g(v,i)$。
那么答案就是减去：
$$
\sum_{i=1}^n \sum_{j=\lceil \frac{i}{2} \rceil}^{\min(i,sz(v))} f(v,j) \cdot g(u,i-j)
$$
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=5e3;
const int mod=10007;
int n;
vector<int> E[maxn+5];
int sz[maxn+5],mx[maxn+5];
int wg[2];
int f[maxn+5][maxn+5];
int g[maxn+5][maxn+5];
int ans;
void Dfs(int u,int fa){
sz[u]=1;
for(int v:E[u]){
if(v==fa) continue;
Dfs(v,u);
sz[u]+=sz[v];
mx[u]=max(mx[u],sz[v]);
}
mx[u]=max(mx[u],n-sz[u]);
if(mx[u]<=n/2) wg[bool(wg[0])]=u;
}
void DfsF(int u,int fa){
f[u][1]=1;
sz[u]=1;
for(int v:E[u]){
if(v==fa) continue;
DfsF(v,u);
sz[u]+=sz[v];
for(int i=sz[u];i;i--)
for(int j=1;j<=sz[v]&&j<=i;j++)
f[u][i]=(f[u][i]+f[u][i-j]*f[v][j])%mod;
}
}
signed main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
int u,v;
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
E[u].push_back(v),E[v].push_back(u);
}
Dfs(1,0);
if(wg[1]){
DfsF(wg[0],wg[1]);
DfsF(wg[1],wg[0]);
for(int i=1;i<=sz[wg[0]]&&i<=sz[wg[1]];i++)
ans=(ans+f[wg[0]][i]*f[wg[1]][i])%mod;
}
else{
u=wg[0],DfsF(u,0);
for(int i=1;i<=n;i++)
ans=(ans+f[u][i])%mod;
for(int v:E[u]){
for(int i=1;i<=n;i++){
g[v][i]=f[u][i];
for(int j=1;j<=sz[v]&&j<=i;j++)
g[v][i]=(g[v][i]-g[v][i-j]*f[v][j])%mod;
for(int j=ceil(i/2.0);j<=i&&j<=sz[v];j++)
ans=(ans-g[v][i-j]*f[v][j])%mod;
}
}
}
printf("%d",(ans+mod)%mod);
return 0;
}
|