http://poj.org/problem?id=1655

POJ1655.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;

const int N = int(1e5) + 9;
const int INF = 0x3fffffff;

struct edge {
    int a, b, w;
    bool del;
    void in() {
        scanf("%d %d", &a, &b);
    }
} E[N];

vector<int> adj[N];
int sz[N];
int n, k, c, cc, nn; LL z;

map<int, int> H, S;

void dfsc(int u, int p = -1) {
    
  //  cout << u << endl;
    
    sz[u] = 1;
    int ss = 0;
    // for (auto i: adj[u]) {
    for (int ii=0;ii<adj[u].size();++ii ) {
        int i = adj[u][ii];
        if (E[i].del) continue;
        int v = E[i].a ^ E[i].b ^ u;
        if (v == p) continue;
        dfsc(v, u);
       // cout << u << " " << v << endl;
        sz[u] += sz[v];
        ss = max(ss, sz[v]);
    }
    
   // cout << u << ": " << nn << " " << sz[u] << endl;
    
    ss = max(ss, nn - sz[u]);
    if (ss < cc || ss == cc && u < c) {
        cc = ss;
        c = u;
    }
}

void stat(int d = 1) {
    // LL z = 0;
    // a + b <= k;
    /*int n = H.size();
    
    REP(i, n) {
    }*/
}

void gao(int u = 1) {
    cc = INF, dfsc(u);
    cout << c << " " << cc << endl;
    
    /*H.clear(); dfs0(c); stat();
    
    for (auto i: adj[u]) {
        if (E[i].del) continue;
        int v = E[i].a ^ E[i].b ^ u;
        H.clear(); dfs1(v); stat(-1);
        gao();
    }*/
}


int main() {
    
#ifndef ONLINE_JUDGE
    freopen("/users/minakokojima/Documents/github/ACM-Training/Workspace/in.txt", "r", stdin);
    //freopen("/users/minakokojima/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

//    while (~scanf("%d %d", &n, &k)) {
    int T; cin >> T; for (int i=0;i<T;++i) {
        scanf("%d", &n);
//        if (n == 0) break;
        for (int i=1;i<=n;++i) adj[i].clear();
        
        for (int i=0;i<n-1;++i) {
            E[i].in();
            adj[E[i].a].push_back(i);
            adj[E[i].b].push_back(i);
        }
        
        nn = n, z = 0, gao();
        //cout << z << endl;
    }
}