题解-FJOI2014 树的重心

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;

}

祝大家学习愉快！

巴特西

题解-FJOI2014 树的重心

最新文章

热门文章