lp4582 FJOI2014 树的重心

两个重心的情况想想都麻。我们首先考虑一个重心的情况。 我们把 假设我们现在已经求出了每个子树的大小，那么我们发现，一棵子树有且仅有它的大小是对答案有影响的。所以我们可以预处理出每棵子树的不同大小的联通结构数，然后枚举子树大小瞎统计一下。 那么想想要怎么预处理。我们令\(f_{i,j}\)表示以\(i\)为根节点的子树中选取\(j\)个节点的联通子树的个数，\(g_{i,j}\)表示当前子树前\(i\)个儿子选取\(j\)个的联通子树的个数。 那么，根据定义我们有： $$g_{nw,j}=\sum_{k=1}^{j}g_{nw-1,k}f_{v,j-k}$$ $$f_{X,i}=g_{sum\_of\_sons,i-1}$$ 然后树形DP即可。 仔细想想，如果有两个重心，那么把两个重心的连边断开，两边的答案的统计是互不干扰的。 故而我们可以将原树分成两棵树统计答案，再把答案相乘。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(A,X) for(int A=h[X];A;A=e[A].nxt)

const int MOD=10007;
const int INF=0x3f3f3f3f;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[404];
int h[205],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}
int sz[205],mx[205],rt=0,rt2=0,totsz,Tid=0,n;
inline void dfs0(int X,int FA){
	sz[X]=1;mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],totsz-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
		rt2=0;
	}else if(mx[X]==mx[rt]){
		rt2=X;
	}
}
int f[205][205],g[205][205];
inline void dfs1(int X,int FA){
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs1(e[i].v,X);
	}
	for(int i=0;i<=n;++i){
		for(int j=0;j<=n;++j){
			g[i][j]=0;
		}
	}
	f[X][1]=f[X][0]=g[0][0]=sz[X]=1;
	int nw=1;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		sz[X]+=sz[e[i].v];
		for(int j=0;j<=sz[X];++j){
			for(int k=0;k<=j;++k){
				g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[i].v][k]%MOD)%MOD;
			}
		}
		++nw;
	}
	--nw;
	for(int i=1;i<=sz[X];++i){
		f[X][i]=g[nw][i-1];
	}
}
int ans=0;
inline void calc1(){
	ans=1;
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,0);
	for(int i=2;i<=n;++i){
		for(int j=0;j<=n;++j){
			for(int k=0;k<=n;++k){
				g[j][k]=0;
			}
		}
		g[0][0]=1;int nw=1;sz[rt]=1;
		Fv(E,rt){
			sz[rt]+=sz[e[E].v];
			for(int j=0;j<=Min(i-1,sz[rt]);++j){
				for(int k=0;k<=j;++k){
					if(2*k>=i){
						break;
					}
					g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[E].v][k]%MOD)%MOD;
				}
			}
			++nw;
		}
		--nw;
		ans=(ans+g[nw][i-1])%MOD;
	}
}
inline void calc2(){
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,rt2);dfs1(rt2,rt);
	ans=0;
	for(int i=1;i<=n/2;++i){
		ans=(ans+f[rt][i]*f[rt2][i]%MOD)%MOD;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	et=rt=rt2=0;
	for(int i=1;i<=n;++i){
		h[i]=sz[i]=0;
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	totsz=n;
	mx[0]=INF;
	dfs0(1,0);
	if(!rt2){
		calc1();
	}else{
		calc2();
	}
	printf("Case %d: %d\n",Tid,ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		++Tid;
		init();
	}
	return 0;
}