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

Source

求树的重心。！

树的重心性质是以该点为根的有根树最大子树的结点数最少，也就是让这树更加"平衡"，easy知道这样全部的子树的大小都不会超过整个树大小的一半，所以在树分治时防止树退化成链非常实用。

。

求树的重心做法是dfs简单的树dp即可。设son[i]表示以i为根的子树的结点数(包含i,叶子结点就是1),那么son[i]就+=sum(son[j])...然后求以i为根的最大结点数就是max(son[j],n-son[i])，n-son[i]是i的"上方结点"的个数。

关于树的重心一些性质:http://fanhq666.blog.163.com/blog/static/81943426201172472943638/

代码：

/**

 * @author neko01

 */

//#pragma comment(linker, "/STACK:102400000,102400000")

#include <cstdio>

#include <cstring>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cmath>

#include <set>

#include <map>

using namespace std;

typedef long long LL;

#define min3(a,b,c) min(a,min(b,c))

#define max3(a,b,c) max(a,max(b,c))

#define pb push_back

#define mp(a,b) make_pair(a,b)

#define clr(a) memset(a,0,sizeof a)

#define clr1(a) memset(a,-1,sizeof a)

#define dbg(a) printf("%d\n",a)

typedef pair<int,int> pp;

const double eps=1e-9;

const double pi=acos(-1.0);

const int INF=0x3f3f3f3f;

const LL inf=(((LL)1)<<61)+5;

const int N=20005;

struct node{

    int to,next;

}e[N*2];

int head[N];

int son[N];  //son[i]表示以i为根的子树节点个数包含i

int dp[N];   //dp[i]表示以i为根时的最大子树节点数

int tot;

int n;

void init()

{

    tot=0;

    clr1(head);

}

void add(int u,int v)

{

    e[tot].to=v;

    e[tot].next=head[u];

    head[u]=tot++;

}

void dfs(int u,int pre)

{

    son[u]=1;

    dp[u]=0;

    for(int i=head[u];i!=-1;i=e[i].next)

    {

        int v=e[i].to;

        if(v!=pre)

        {

            dfs(v,u);

            son[u]+=son[v];

            dp[u]=max(dp[u],son[v]);

        }

    }

    dp[u]=max(dp[u],n-son[u]);

}

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);

            add(u,v);

            add(v,u);

        }

        dfs(1,0);

        int ans1=0,ans2=n+1;

        for(int i=1;i<=n;i++)

            if(dp[i]<ans2)

            {

                ans2=dp[i];

                ans1=i;

            }

        printf("%d %d\n",ans1,ans2);

    }

    return 0;

}