poj

#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 20000 + 233;
int T, n;
vector<int> G[maxn];
int sz[maxn], son[maxn];
int ans, res;

void (){
    for(int i = 1; i <= n; i++) G[i].clear();
    res = 1e9, ans = 0;
}

void dfs(int u, int f){
    sz[u] = 1, son[u] = 0;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v == f) continue;
        dfs(v, u);
        sz[u] += sz[v];
        son[u] = max(son[u], sz[v]);
    }
    son[u] = max(son[u], n - sz[u]);
    if(son[u] < res){
        res = son[u];
        ans = u;
    }
}

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        init();
        for(int i = 1; i < n; i++){
            int u, v;
            scanf("%d %d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1, 0);
        printf("%d %dn", ans, res);
    }
    return 0;
}