简单树形dp-poj-1655-Balancing Act
题目链接：
http://poj.org/problem?id=1655
题目意思：
给一棵树，求去掉一个节点，形成的多棵树中节点数的最大值最小。
解题思路：
简单树形dp.
dp[i]表示儿子中节点数最多的分支节点数。
sum[i]表示i为根的子树节点总数。
第一遍dfs求出dp和sum,第二遍dfs枚举去掉的节点，max(dp[cur],from) //from表示从父亲方向过来节点数，向下的时候from+sum[cur]-sum[v].
代码：
#include <iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cmath>#define INF 0x3f3f3f3fusing namespace std;#define Maxn 21000int dp[Maxn],cnt,n,nuans,node;int sum[Maxn];struct Edge{ int v; struct Edge * next;}edge[Maxn<<1],*head[Maxn<<1];void add(int a,int b){ ++cnt; edge[cnt].v=b; edge[cnt].next=head[a]; head[a]=&edge[cnt];}void dfs1(int cur,int fa){ struct Edge * p=head[cur]; dp[cur]=0; sum[cur]=1; while(p) { int v=p->v; if(v!=fa) { dfs1(v,cur); dp[cur]=max(dp[cur],sum[v]);//表示节点数最多的儿子分支 sum[cur]+=sum[v]; //以该点为根的子树的总的节点数 } p=p->next; }}void dfs2(int cur,int fa,int from){ struct Edge * p=head[cur]; //if(dp[cur]&&from) int tt=max(dp[cur],from); if(tt<nuans) { nuans=tt; node=cur; } else if(tt==nuans&&cur<node) node=cur; while(p) { int v=p->v; if(v!=fa) dfs2(v,cur,from+sum[cur]-sum[v]); //from表示父亲方向节点总数 p=p->next; }}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(head,NULL,sizeof(head)); cnt=0; for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } dfs1(1,-1); /* for(int i=1;i<=n;i++) printf("i:%d %d %d\n",i,dp[i],sum[i]);*/ nuans=INF; dfs2(1,-1,0); printf("%d %d\n",node,nuans); } return 0;}