poj 1655 Balancing Act 树状DP，求树的质心

传送门：Balancing Act

题目大意

有N个节点的无根树，每两个节点之间只有一条边，求删除一个节点之后最大的联通块(节点数最多)！

解题思路

先任意选择一个节点作为根节点，这样就能把一颗无根树变为有根树了，然后设sum[i]表示已i节点为根节点的子树的节点个数。 那么删除节点i会有多少个联通块呢？ i节点有多少孩子节点就有多少联通块还有i的父节点也是一个联通块！ 如下图所示： 比如说E节点： sum[E] = 3; dp[E] = 9-sum[E]; 对于B节点： sum[B] = 7; dp[B] = 3 这个过程是可以通过一次DFS完成的！ 每次先递归到叶子节点，然后从叶子节点向根节点开始找，不断地更新dp和sum值！

AC代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 20000 + 500; const int INF = 0x3f3f3f3f; int head[MAXN],e,N,sum[MAXN],dp[MAXN]; bool vis[MAXN]; struct Edge{ int v,nxt,w; }E[MAXN<<1]; void init() { e = 0; memset(vis,false,sizeof vis); memset(head,-1,sizeof head); memset(sum,0,sizeof sum); memset(dp,INF,sizeof dp); } void add(int u,int v) { E[e].v = v; E[e].nxt = head[u]; head[u] = e++; } void DFS(int u,int pre) { for(int i=head[u];~i;i=E[i].nxt){ int v = E[i].v; if(pre == v)continue; DFS(v,u); sum[u]+=sum[v]; } dp[u] = N-1-sum[u]; for(int i=head[u];~i;i=E[i].nxt){ int v = E[i].v; if(pre==v) continue; dp[u] = max(dp[u],sum[v]); } sum[u]++; } int main() { int T; int u,v; //freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { init(); scanf("%d",&N); for(int i=1;i<N;i++){ scanf("%d%d",&u,&v); add(u,v);add(v,u); } DFS(1,0); int p,ans=INF; for(int i=1;i<=N;i++){ if(dp[i]<ans){ p = i; ans = dp[i]; } } printf("%d %d\n",p,ans); } return 0; }