POJ 1655 Balancing Act (树形dp 树的重心)

Balancing Act

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 10596		Accepted: 4398

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

The first line of input contains a single integer t (1 <= t <= 20), the number of test cases. The first line of each test case contains an integer N (1 <= N <= 20,000), the number of congruence. The next N-1 lines each contains two space-separated node numbers that are the endpoints of an edge in the tree. No edge will be listed twice, and all edges will be listed.

Output

For each test case, print a line containing two integers, the number of the node with minimum balance and the balance of that node.

Sample Input

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

Sample Output

1 2

Source

POJ Monthly--2004.05.15 IOI 2003 sample task

题目链接：http://poj.org/problem?id=1655

题目大意：定义平衡数为去掉一个点其最大子树的结点个数。求给定树的最小平衡数和相应要删的点

题目分析：事实上就是求树的重心。找到一个点，其全部的子树中最大的子树的节点数最少，那么这个点就是这棵树的重心。删除重心后。剩余的子树更加平衡正好满足题意，以下说明怎样求重心，由于这是一棵无根树，因此要连双向边，任取一个顶点作为根。记dp[i]为以结点i为子树根的子树的结点个数（注意这里不包含子树根本身），所以
dp[i] += dp[son] + 1。加1是由于要算上其儿子自己这个结点，然后对于每一个子树求出来的dp[son] + 1我要取最大。设最大为b，注意这里还要再取一次最大
b = max(b, n - dp[i] - 1)，由于这是一棵无根树。当前结点i也能够做这棵树的根。所以这里把剩余部分也当作它的儿子（即在当前dfs序下的其祖先和兄弟部分）画个图能够看的更明确些

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 20005;
int const INF = 0x3fffffff;

struct EDGE
{
    int to, next;
}e[MAX * 2];

int head[MAX], dp[MAX];
bool vis[MAX];
int n, cnt, num, ans, b;

void Add(int u, int v)
{
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt ++;
}

void Init()
{
    cnt = 0;
    n = 0;
    num = INF;
    ans = n;
    memset(head, -1, sizeof(head));
    memset(dp, 0, sizeof(dp));
    memset(vis, false, sizeof(vis));
}

void DFS(int rt)
{
    vis[rt] = true;
    dp[rt] = 0;
    int b = 0;
    for(int i = head[rt]; i != -1; i = e[i].next)
    {
        int son = e[i].to;
        if(!vis[son])
        {
            DFS(son);
            dp[rt] += dp[son] + 1;
            b = max(b, dp[son] + 1); 
        }
    }
    b = max(b, n - dp[rt] - 1);
    if(b < num || (b == num && rt < ans))
    {
        num = b;
        ans = rt;
    }
    return; 
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        Init();
        int st;
        scanf("%d", &n);
        for(int i = 0; i < n - 1; i++)
        {
            int u, v;
            scanf("%d %d", &u, &v);
            Add(v, u);   
            Add(u, v);
            st = u;
        }
        DFS(st);
        printf("%d %d
", ans, num);
    }
}