poj 1655 树形dp求取树的重心

http://poj.org/problem?id=1655

Description

Consider a tree T with N (1 <= N <= 20,000) nodes numbered 1...N. Deleting any node from the tree yields a forest: a collection of one or more trees. Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node from T. 
For example, consider the tree: 

Deleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6}, {3,7}, and {4,5}. Each of these trees has two nodes, so the balance of node 1 is two. 

For each input tree, calculate the node that has the minimum balance. If multiple nodes have equal balance, output the one with the lowest number. 

Input

Output

Sample Input

1
7
2 6
1 2
1 4
4 5
3 7
3 1

Sample Output

1 2

/**
poj 1655  利用树形dp求树的重心
题目大意：求数的重心
解题思路：树的重心定义为:找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重
          心后，生成的多棵树尽可能平衡.  实际上树的重心在树的点分治中有重要的作用, 可以避免N^2的极端复杂度（从退化链的一端出发），保证
          NlogN的复杂度, 利用树形dp可以很好地求树的重心.
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=20005;

struct note
{
    int v,next;
}edge[maxn*2];

int head[maxn],ip;
int maxx,point,n,num[maxn];

void init()
{
    memset(head,-1,sizeof(head));
    ip=0;
}

void addedge(int u,int v)
{
    edge[ip].v=v,edge[ip].next=head[u],head[u]=ip++;
}

void dfs(int u,int pre)
{
    int tmp=-0x3f3f3f3f;
    num[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==pre)continue;
        dfs(v,u);
        num[u]+=num[v];
        tmp=max(tmp,num[v]);
    }
    tmp=max(tmp,n-num[u]);///除去以u为根节点的子树部分剩下的节点数
    if(tmp<maxx||tmp==maxx&&u<point)
    {
        point=u;
        maxx=tmp;
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        init();
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        memset(num,0,sizeof(num));
        maxx=0x3f3f3f3f;
        dfs(1,-1);
        printf("%d %d\n",point,maxx);
    }
    return 0;
}

poj 1655 树形dp求取树的重心

原文：http://blog.csdn.net/lvshubao1314/article/details/43815747