传送门：http://poj.org/problem?id=1655

题意：有T组数据，求出每组数据所构成的树的重心，输出这个树的重心的编号，并且输出重心删除后得到的最大子树的节点个数，如果个数相同，取编号小 的

思路：树的重心的模板题

首先要知道什么是树的重心,树的重心定义为:找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡.  

所以寻找重心，即是最小化重心的最大子树。子树大小的计算分为两部分

1. 的下面的子树大小，即可计算出
2. 的上面的子树大小，则为 （n为总结点的个数，d即是的所有子树大小，包含）

，最后取里面的最小值，即为该树的重心位置

代码：

#include<iostream>

#include<cstdio>

using namespace std;

const int maxn = 20005;

//邻接表存图

struct node

{

    int to;

    int next;

};

node edges[maxn << 1];

int head[maxn];

int d[maxn];//树的深度

int dp[maxn];

int tot;

int n;

int ans;

void add_edges(int u, int v)

{

    edges[++tot].to = v;

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

    head[u] = tot;

}

void dfs(int root, int fa)

{

    int mx = 0;

    for(int i = head[root]; i; i = edges[i].next)

    {

        int v = edges[i].to;

        if(v == fa)

            continue;

        else

        {

            dfs(v, root);

            d[root] += d[v];

            mx = max(d[v], mx);

        }

    }

    dp[root] = max(n - d[root], mx);

    if(dp[ans] > dp[root])

    {

        ans = root;

    }

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%d", &n);

        tot = 0;

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

            head[i] = 0;

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

            d[i] = 1;

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

        {

            int a, b;

            scanf("%d %d", &a, &b);

            add_edges(a, b);

            add_edges(b, a);

        }

        ans = 0;

        dp[ans] = 0x3f3f3f3f;

        dfs(1, 0);

        cout << ans << " " << dp[ans] << endl;

    }

}