Balancing Act

 POJ - 1655 

 

求树的重心。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;
const int N = 2e4 + 5;
vector<int> g[N];
int ma[N], num[N];
int n;

//根据树的重心的定义，我们发现判断一个点是不是重心 只要把这个点去掉 
//看它剩下的子树结点的个数的最大值是不是最小就ok了 
//子树有两种：一个是往下的即ma[i]，另一个是往上的 即n - num[i]


void dfs(int u, int f) {
    num[u] = 1;
    ma[u] = 0;
    int len = g[u].size();
    for(int i = 0; i < len; i++) {
        int v = g[u][i];
        if(v == f) continue;
        dfs(v, u);
        ma[u] = max(ma[u], num[v]);
        num[u] += num[v];
    }
    ma[u] = max(ma[u], n - num[u]);
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int u, v;
        for(int i = 1; i <= n; i++) g[i].clear();
        for(int i = 1; i < n; i++) {
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, 0);
        int mi = N, ind = 0;
        for(int i = 1; i <= n; i++) {
            if(ma[i] < mi) {
                mi = ma[i];
                ind = i;
            }
        }
        printf("%d %d\n", ind, mi);
    }
    return 0;
}