树形DP(3)求树的重心

胡乱分析

定义:树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。
也就是说第一步要去寻找所有的子树中的最大的子树节点，第二步去比较这个值与总的大小即可

代码(poj 3107 Godfather)

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int maxn[600005],sum[600005],head[600005],minn=99999999,n,cnt=1;
struct node
{
  int v,next;
}G[600005];
void add(int st,int ed)
{
  G[cnt].v=ed;
  G[cnt].next=head[st];
  head[st]=cnt++;
}
int dfs(int p,int fa)
{
  if(sum[p]) //剪枝
  return sum[p];
  sum[p]=1; //初始化每个节点都具有1
  for(int i=head[p];i;i=G[i].next)
  {
    if(G[i].v!=fa) //链式前向星遍历所有的边
    {
      sum[p]+=dfs(G[i].v,p); //sum遍历所有的子树
      maxn[p]=max(maxn[p],sum[G[i].v]); //回溯记录每个节点的maxn
    }
  }
  maxn[p]=max(maxn[p],n-sum[p]); //这里还要找一下父亲部分，儿子部分和父亲部分比一个最大值
  minn=min(minn,maxn[p]); //然后寻找答案最小值即可
  return sum[p];
}
int main()
{
  cin>>n;
  for(int i=1;i<=n-1;i++)
  {
    int st,ed;
    scanf("%d%d",&st,&ed);
    add(st,ed);
    add(ed,st);
  }
  dfs(1,1);
  for(int i=1;i<=n;i++)
  if(maxn[i]==minn)
  cout<<i<<" ";
}