poj 1655 Balancing Act（求树的重心）

在一棵树中，去掉一个点，使得剩下的每一颗树的结点数最多的那颗树，结点数最少。

具体解法看注释.

/*
    定义dp[i]为去掉i结点，剩下的树里，结点最多的那颗树的结点数。
    可分为2类情况。
    1、由于i结点的儿子结点都成了一棵树的根节点，所以dp[i] = (i的每个儿子所拥有的结点数，的最大值)。
    2、而另一种情况就是剩下的那棵树，所以dp[i] = N-num[i]。
    其中num[i]表示以i为根的树的所有结点数，可以dfs求出。
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define MAXN 20005
int N;
vector<int> node[20005];
int num[MAXN];
int dp[MAXN];
bool vis[MAXN]; //由于为无向图，所以用这个来标记此结点是否计算过。

int dfs(int id)
{
    int n=node[id].size();
    vis[id]=1;
    num[id]=1;
    for(int i=0;i<n;i++)
    {
        if(!vis[node[id][i]])
        num[id]+=dfs(node[id][i]);
    }
    return num[id];
}
void cal(int id)
{
    int n=node[id].size();
    int k;
    vis[id]=1;
    for(int i=0;i<n;i++)
    {
        k=node[id][i];
        if(vis[k])    //只有可能是它老爸
        {
            dp[id]=max(dp[id],N-num[id]);
        }
        else          //它儿子
        {
            dp[id]=max(dp[id],num[k]);
            cal(k);
        }
    }
}
int main()
{
    int t,a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&N);
        for(int i=1;i<=N;i++)
            node[i].clear();
        memset(dp,0,sizeof(dp));
        for(int i=1;i<N;i++)
        {
            scanf("%d%d",&a,&b);
            node[a].push_back(b);
            node[b].push_back(a);
        }
        memset(vis,0,sizeof(vis));
        dfs(1);
        memset(vis,0,sizeof(vis));
        cal(1);
        int ans=0x7fffffff;
        int k;
        for(int i=1;i<=N;i++)
        {
            if(dp[i]<ans)
            {
                ans=dp[i];
                k=i;
            }
        }
        printf("%d %d\n",k,ans);
    }
    return 0;
}