首页 > 代码库 > HDU 4863 Centroid of a Tree
HDU 4863 Centroid of a Tree
树的重心，树形$dp$，背包。
树的重心有两个充分必要条件：
$1$.某树有两个重心$a$，$b$ $<=>$ $a$与$b$相邻，断开$a$与$b$之间的边之后，两个联通分量内的点的个数相同。
$2$.某树有一个重心$a$ $<=>$ 以$a$为根的树，去掉a之后，剩下的联通分量，除去节点个数最多的联通分量后，剩余的联通分量节点个数之和大于等于最大的联通分量的节点个数。
因此，可以先计算出初始树的重心，分两种情况讨论。
如果有两个重心$a$，$b$，那么，我们需要计算出断开$a$,$b$之间的边，以$a$为根的树以及以$b$为根的树中包含$x$个节点的树有几种，然后枚举$x$两边相乘求和就是答案了。
如果只有一个重心$a$，这种情况比两个重心的复杂一点，需要计算以$a$为根的树有多少种满足充要条件$2$，先要计算出以$a$的儿子为根的树中包含$x$个节点的树有几种，然后再用背包去算一下反面的情况，总的方案减去反面的就是答案。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0);void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}int T,n;int mod=10007;int dp[205][205];int c[205],mx[205],k[205],f[205];vector<int>tmp[205],t[205],zx;void init(){ memset(dp,0,sizeof dp); memset(c,0,sizeof c); memset(mx,0,sizeof mx); memset(f,0,sizeof f); for(int i=1;i<=n;i++) tmp[i].clear(); for(int i=1;i<=n;i++) t[i].clear(); zx.clear();}void D(int x){ f[x]=1; for(int i=0;i<tmp[x].size();i++) { if(f[tmp[x][i]]) continue; t[x].push_back(tmp[x][i]); D(tmp[x][i]); }}void F(int x){ for(int i=0;i<t[x].size();i++) { F(t[x][i]); mx[x]=max(mx[x],c[t[x][i]]); c[x]=c[x]+c[t[x][i]]; } c[x]++;}void G(int x){ f[x]=1; for(int i=0;i<tmp[x].size();i++) { if(f[tmp[x][i]]) continue; if(zx.size()==2&&tmp[x][i]==zx[1]) continue; t[x].push_back(tmp[x][i]); G(tmp[x][i]); }}void DP(int x){ dp[x][0]=1; int h[250],g[250]; memset(h,0,sizeof h); memset(g,0,sizeof g); g[0]=1; for(int i=0;i<t[x].size();i++) { DP(t[x][i]); for(int j=0;j<=c[x]+c[t[x][i]];j++) h[j]=0; for(int p1=c[x];p1>=0;p1--) for(int p2=c[t[x][i]];p2>=0;p2--) h[p1+p2]=(h[p1+p2]+g[p1]*dp[t[x][i]][p2]%mod)%mod; for(int j=0;j<=c[x]+c[t[x][i]];j++) g[j]=h[j]; c[x]=c[x]+c[t[x][i]]; } c[x]++; for(int i=1;i<=200;i++) dp[x][i]=g[i-1];}int main(){ scanf("%d",&T); int cas=1; while(T--) { scanf("%d",&n); init(); for(int i=1;i<=n-1;i++) { int x,y; scanf("%d%d",&x,&y); tmp[x].push_back(y); tmp[y].push_back(x); } D(1); F(1); for(int i=1;i<=n;i++) k[i]=max(mx[i],n-c[i]); int mn=400; for(int i=1;i<=n;i++) mn=min(mn,k[i]); for(int i=1;i<=n;i++) if(k[i]==mn) zx.push_back(i); for(int i=1;i<=n;i++) t[i].clear(); memset(f,0,sizeof f); G(zx[0]); if(zx.size()==2) G(zx[1]); memset(c,0,sizeof c); DP(zx[0]); if(zx.size()==2) DP(zx[1]); printf("Case %d: ",cas++); int ans=0; if(zx.size()==1) { int h[250],g[250]; int fm=0; for(int i=0;i<t[zx[0]].size();i++) { memset(h,0,sizeof h); memset(g,0,sizeof g); g[0]=1; int a=0; for(int j=0;j<t[zx[0]].size();j++) { if(i==j) continue; for(int w=0;w<=a+c[t[zx[0]][j]];w++) h[w]=0; for(int p1=a;p1>=0;p1--) for(int p2=c[t[zx[0]][j]];p2>=0;p2--) h[p1+p2]=(h[p1+p2]+g[p1]*dp[t[zx[0]][j]][p2]%mod)%mod; a=a+c[t[zx[0]][j]]; for(int j=0;j<=200;j++) g[j]=h[j]; } for(int j=0;j<=c[t[zx[0]][i]];j++) for(int w=0;w<j;w++) fm=(fm+dp[t[zx[0]][i]][j]*g[w]%mod)%mod; } for(int i=1;i<=n;i++) ans=(ans+dp[zx[0]][i])%mod; printf("%d\n",(ans-fm+mod)%mod); } else { for(int i=1;i<=200;i++) ans=(ans+dp[zx[0]][i]*dp[zx[1]][i]%mod)%mod; printf("%d\n",ans); } } return 0;}
HDU 4863 Centroid of a Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。