POJ 1655 Balancing Act【树的重心模板题】

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

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

思路：树的重心的模板题

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

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

$x$ 的下面的子树大小， $dfs$ 即可计算出
$x$ 的上面的子树大小，则为 $n-d[x]$ （n为总结点的个数，d即是 $x$ 的所有子树大小，包含 $x$ ）

$dp[x]=max(n-d[x],d[y]),(yin x)$ ，最后取 $dp$ 里面的最小值，即为该树的重心位置

代码：

#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;
    }
}