自动搬运

查看原文

来自洛谷，原作者为

	George1123 **

搬运于2025-08-24 22:01:37，当前版本为作者最后更新于2020-06-10 17:32:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\Huge\color{#814514}{\tt My~Cnblogs}$

---

FJOI2014 树的重心

$Q$ 组测试数据。给一棵树大小为 $n$，求有多少个子树与其重心相同。重心可能有多个。

数据范围：$1\le Q\le 50$，$1\le n\le 200$。

---

就是要写好几个 $\tt dp$ 吧，细节比较多。

---

先 $\tt Dfs$ 一次找个重心：

int sz[N+7],g[N+7];
int Dfs1(int u,int fa){
	int res=inf;
	sz[u]=1,g[u]=0;
	for(int&v:e[u])if(v!=fa){
		res=min(res,Dfs1(v,u));
		sz[u]+=sz[v],g[u]=max(g[u],sz[v]);
	}
	g[u]=max(g[u],n-sz[u]);
	res=min(res,g[u]);
	return res;
}
//...
int ms=Dfs1(1,0);
vector<int> G;
for(int i=1;i<=n;i++)if(g[i]==ms) G.pb(i);

重心只有 $1$ 个或 $2$ 个，于是分类讨论 。

---

• 有 $2$ 个重心

设重心为 $Gx$ 和 $Gy$。

所以必然有边 $(Gx,Gy)$。

把 $(Gx,Gy)$ 断开后两部分子树必然是相等的（要不然就只有 $1$ 个重心）。

所以可以在两部分子树以 $Gx,Gy$ 为根各写个 $\tt dp$：

$f_{u,i}$ 表示 $u$ 点的子树选 $i$ 个点的联通子树（包括 $u$ 点）的方案数。

$$f_{u,i}=\sum_{v\in son_u}\sum_{j=1}^{\min(i-1,sz_v)}f_{u,i-j}\cdot f_{v,j} $$

然后 $Ans=\sum_{i=1}^{\min(sz_{Gx},sz_{Gy})}f_{Gx,i}\cdot f_{Gy,i}$。

不过写两次树形 $\tt dp$ 麻烦，我的代码中省了个树形 $\tt dp$。

---

• 有 $1$ 个重心

设重心为 $G$。

所以选出子树中 $G$ 点的每个子树大小 $\le$ 所有子树大小之和的 $\frac 12$。

所以可以先如上跑个 $\tt dp$，以 $G$ 为根得出同上的 $f_{i,j}$。

$F_{i,j}$ 选出子树共 $i$ 个点（除了 $G$），最大子树大小为 $j$ 的方案数。

所以初始化 $F_{i,i}=\sum_{v\in son_G}f_{v,i}$。

$${\rm Then}\forall k\in[1,i]:F_{i,\max(j,k)}+=F_{i-j,k}\cdot f_{v,j} $$

最后 $Ans=1+\sum_{i=1}^n\sum_{j=1}^n[2j\le i]F_{i,j}$。

为什么要 $+1$？表示只选 $G$ 点的情况。

---

• 代码

#include <bits/stdc++.h>
using namespace std;

//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair(a,b)
#define x first
#define y second
#define b(a) a.begin()
#define e(a) a.end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

//Data
const int N=200,P=1e4+7;
int n;
vector<int> e[N+7];

//Treedp
int sz[N+7],g[N+7],f[N+7][N+7];
int Dfs1(int u,int fa){
	int res=inf;
	sz[u]=1,g[u]=0;
	for(int&v:e[u])if(v!=fa){
		res=min(res,Dfs1(v,u));
		sz[u]+=sz[v],g[u]=max(g[u],sz[v]);
	}
	g[u]=max(g[u],n-sz[u]);
	res=min(res,g[u]);
	return res;
}
void Dfs2(int u,int fa){
	sz[u]=f[u][0]=f[u][1]=1;
	for(int&v:e[u])if(v!=fa){
		Dfs2(v,u),sz[u]+=sz[v];
		for(int i=sz[u];i>=1;i--)
			for(int j=1;j<=min(sz[v],i-1);j++)
				(f[u][i]+=f[u][i-j]*f[v][j]%P)%=P;			
	}
}

//KonnyWen
int F1[N+7][N+7],F2[N+7];
int KonnyWen(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) e[i].clear();
	for(int i=1,u,v;i<=n-1;i++){
		scanf("%d%d",&u,&v);
		e[u].pb(v),e[v].pb(u);
	}
	int ms=Dfs1(1,0);
	vector<int> G;
	for(int i=1;i<=n;i++)if(g[i]==ms) G.pb(i);
//	puts("G:");
//	for(int&x:G) printf("%d ",x);puts("");
	memset(f,0,sizeof f),Dfs2(G[0],0);
//	puts("f:");
//	for(int i=1;i<=n;i++)
//		for(int j=1;j<=n;j++)
//			printf("%d%c",f[i][j],"\n "[j<n]);
	int sm=0,res=0; 
	if(sz(G)==1){
		memset(F1,0,sizeof F1),ms=-inf;
		for(int&v:e[G[0]]){
			ms=max(ms,sz[v]),sm+=sz[v];
			for(int i=sm;i>=1;i--)
				for(int j=min(sz[v],i);j>=1;j--){
					if(j==i) (F1[i][j]+=f[v][j])%=P;
					else for(int k=1;k<=min(i,ms);k++)
						(F1[i][max(j,k)]+=F1[i-j][k]*f[v][j]%P)%=P;
				}
		}
//		puts("F1:");
//		for(int i=1;i<=n;i++)
//			for(int j=1;j<=n;j++)
//				printf("%d%c",F1[i][j],"\n "[j<n]);
		for(int i=1;i<=sm;i++)
			for(int j=1;j<=i;j++)
				if(j*2<=i) (res+=F1[i][j])%=P;
		res++;
	} else if(sz(G)==2){ //一次树形 dp 代替两次
		memset(F2,0,sizeof F2),F2[0]=1;
		for(int&v:e[G[0]])if(v!=G[1]){
			sm+=sz[v];
			for(int i=sm;i>=1;i--)
				for(int j=1;j<=min(sz[v],i);j++)
					(F2[i]+=F2[i-j]*f[v][j]%P)%=P;
		}
//		puts("F2:");
//		for(int i=1;i<=n;i++) printf("%d ",F2[i]);puts("");
		for(int i=1;i<=sm+1;i++)
			(res+=F2[i-1]*f[G[1]][i]%P)%=P;
	}
	return res;	
}

//Main
int main(){
	int t; scanf("%d",&t);
	for(int i=1;i<=t;i++) 
		printf("Case %d: %d\n",i,KonnyWen());
	return 0;
}

---

祝大家学习愉快！