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

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

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

$$f[i,j]+=(f[i,j-k]*f[son,k])$$

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

$$g[i,j]+=g[i-1,j-k]*f[son[i],k]\quad k\in[1,j/2]$$

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

$$g[i,j,k+t]+=f[son[i],k]*g[i-1,min(j,Size[son[i-1]]),t]$$ $$Ans+=g[tot,i,j]-g[tot,i-1,j]\quad j\in[2*i,n]$$

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

至此，问题解决。

---

代码

#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;
}