POJ1655 Balancing Act(树的重心)

题目链接 Balancing Act

就是求一棵树的重心，然后统计答案。

#include <bits/stdc++.h>using namespace std;#define REP(i,n)                for(int i(0); i <  (n); ++i)
#define for_edge(i,x)           for(int i = H[x]; i; i = X[i])const int INF = 1 << 30;
const int N     =    100000      +       10;int H[N << 1], E[N << 1], X[N << 1];
int T, et, n, x, y;
int son[N];
int ans_size, ans;inline void addedge(int a, int b){
    E[++et] = b, X[et] = H[a], H[a] = et;
    E[++et] = a, X[et] = H[b], H[b] = et;
}void dfs(int x, int fa){
    int sn = 0;
    for_edge(i, x){
        int u = E[i];
        if (u != fa){
            dfs(u, x);
            son[x] += son[u];
            sn = max(sn, son[u]);
        }
    }
    ++son[x];
    sn = max(sn, n - son[x]);
    if (ans_size > sn || ans_size == sn && ans > x){
        ans_size = sn;
        ans = x;
    }}int main(){    scanf("%d", &T);
    for (; T--;){
        ans_size = INF; ans = INF;
        memset(H, 0, sizeof H);
        memset(son, 0, sizeof son);
        et = 0;
        scanf("%d", &n);
        REP(i, n - 1){
            scanf("%d%d", &x, &y);
            addedge(x, y);
        }
        dfs(1, 0);
        printf("%d %d\n", ans, ans_size);
    }    return 0;}