POJ 1655 Balancing Act

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn = 20010;
 6 struct arc {
 7     int to,next;
 8     arc(int x = 0,int y = -1) {
 9         to = x;
10         next = y;
11     }
12 } e[maxn<<1];
13 int head[maxn],siz[maxn],tot,n;
14 void add(int u,int v) {
15     e[tot] = arc(v,head[u]);
16     head[u] = tot++;
17 }
18 int ret,idx;
19 void dfs(int u,int fa) {
20     siz[u] = 1;
21     int tmp = 0;
22     for(int i = head[u]; ~i; i = e[i].next) {
23         if(e[i].to == fa) continue;
24         dfs(e[i].to,u);
25         tmp = max(siz[e[i].to],tmp);
26         siz[u] += siz[e[i].to];
27     }
28     tmp = max(tmp,n - siz[u]);
29     if(tmp < ret || tmp == ret && u < idx) {
30         ret = tmp;
31         idx = u;
32     }
33 }
34 int main() {
35     int kase,u,v;
36     scanf("%d",&kase);
37     while(kase--) {
38         scanf("%d",&n);
39         memset(head,-1,sizeof head);
40         idx = ret = n<<1;
41         tot = 0;
42         for(int i = 1; i < n; ++i) {
43             scanf("%d%d",&u,&v);
44             add(u,v);
45             add(v,u);
46         }
47         dfs(1,-1);
48         printf("%d %d\n",idx,ret);
49     }
50     return 0;
51 }