「FJOI2014」树的重心 - 树上背包 | Bill Yang's Blog
0%

「FJOI2014」树的重心 - 树上背包

解决此题需要知道重心的性质:
重心$\iff$除去这个点后,最大连通块的点数不超过总点数的一半的点
当我们单独将重心提取出来作为根的时候(重心唯一):

统计所有重心不变的块$\iff$统计所有Core的子树大小不超过总点数的一半的连通块个数
得到目标:从Core的儿子中选出几个连通块,使总点数为i且每个块$\le \frac{i}{2}$的块的个数。
为了得到目标,我们要得到每个Core的子树中选择大小为x的连通块方案数:这明显是一个背包问题
设$f[i,j]$:i的子树中选择大小为j的块的方案数

那么接下来就需要合并Core的儿子结点:
设$g[i,j]$表示前i个儿子,分配j个结点的方案数
可以得到动规方程:

这个方程看似正确,其实有问题:不超过总数一半的限制条件有问题,因为限制条件是动态的。
因此我们要将最大的一棵子树设入状态。
设$g[i,j,k]$表示前i个儿子,最大的儿子结点数不超过j,总共分配k个结点的方案数。
对所有儿子按照Size排个序可以将为$O(n^3)$

另外:对于重心有两个点的情况,易知两个重心相邻,因此可以在它们中间加一个点转为一个重心的情况。

至此,问题解决。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1005,mod=10007;
int T,n,Min,core1,core2,Core,tot,sum,ans,Size[maxn],f[maxn][maxn],g[205][205][205],Maxd[maxn],son[maxn];
bool ifunion;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Clear() {
Min=0x7fffffff/2;
core1=core2=Core=ifunion=tot=sum=0;
ans=1; //只有重心一个点
for(int i=1; i<=n+1; i++)edges[i].clear();
memset(Size,0,sizeof(Size));
memset(Maxd,0,sizeof(Maxd));
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
}
void Dfs(int Now,int father) {
Size[Now]=1;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father)continue;
Dfs(Next,Now);
Size[Now]+=Size[Next];
Maxd[Now]=max(Maxd[Now],Size[Next]);
}
Maxd[Now]=max(Maxd[Now],n-Size[Now]);
if(Maxd[Now]<Min) {
Min=Maxd[Now];
core1=Now;
core2=0;
} else if(Maxd[Now]==Min)core2=Now;
}
void TreeDp(int Now,int father) { //树上背包
Size[Now]=1;
f[Now][0]=f[Now][1]=1;
for(int k=0; k<edges[Now].size(); k++) {
int& Next=edges[Now][k];
if(Next==father)continue;
TreeDp(Next,Now);
Size[Now]+=Size[Next];
for(int i=Size[Now]; i>=1; i--)
for(int j=1; j<i; j++)
f[Now][i]=(f[Now][i]+(f[Now][i-j]*f[Next][j])%mod)%mod;
}
}
bool cmp(const int& a,const int& b) {
return Size[a]<Size[b];
}
int main() {
T=Get_Int();
for(int t=1; t<=T; t++) {
n=Get_Int();
Clear();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Dfs(1,0);
if(core1&&core2) { //将两个重心之间连边变成一个重心
Core=++n;
for(int i=0; i<edges[core1].size(); i++) {
int& Next=edges[core1][i];
if(Next==core2)Next=Core;
}
for(int i=0; i<edges[core2].size(); i++) {
int& Next=edges[core2][i];
if(Next==core1)Next=Core;
}
AddEdge(Core,core1);
AddEdge(Core,core2);
ifunion=1;
} else Core=core1;
TreeDp(Core,0);
for(int i=0; i<edges[Core].size(); i++)son[++tot]=edges[Core][i];
sort(son+1,son+tot+1,cmp);
for(int i=0; i<=200; i++)g[0][i][0]=g[0][i][1]=1;
for(int i=1; i<=tot; i++) {
for(int j=1; j<=Size[son[i]]; j++)
for(int k=0; k<=j; k++)
for(int t=0; t<=sum; t++)
g[i][j][k+t]=(g[i][j][k+t]+f[son[i]][k]*g[i-1][min(j,Size[son[i-1]])][t])%mod;
sum+=Size[son[i]];
}
for(int i=1; i<=Size[son[tot]]; i++)
for(int j=2*i; j<=n; j++)
ans=(ans+g[tot][i][j]-g[tot][i-1][j])%mod;
printf("Case %d: %d\n",t,((ans-ifunion)%mod+mod)%mod);
}
return 0;
}
姥爷们赏瓶冰阔落吧~