poj 1655 Balancing Act

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<queue>
 6 #include<vector>
 7 #include<algorithm>
 8 using namespace std;
 9 
10 vector<int>Q[20002];
11 int num[20002];
12 int dp[20002][2];
13 //DP[I][0] 统计子节点的最大个数
14 //DP[I][1] 统计 自身及子节点 的总个数
15 bool use[20002];
16 void add(int x,int y)
17 {
18     Q[x].push_back(y);
19     num[x]++;
20 }
21 int Max(int x,int y)
22 {
23     return x>y? x:y;
24 }
25 void dfs(int k)
26 {
27     int i,t,cur=0;
28     use[k]=true;
29     dp[k][1]=1;
30     for(i=0;i<num[k];i++)
31     {
32         t=Q[k][i];
33         if(use[t]==true)continue;
34         dfs(t);
35 
36         if(cur<dp[t][1])
37             cur=dp[t][1];
38         dp[k][1]=dp[k][1]+dp[t][1];
39     }
40     dp[k][0]=cur;
41 }
42 int main()
43 {
44     int T;
45     int i,n,x,y,cur,hxl,tom;
46     scanf("%d",&T);
47     while(T--)
48     {
49         scanf("%d",&n);
50         for(i=0;i<=n;i++)
51         {
52             num[i]=0;
53             Q[i].clear();
54         }
55         memset(dp,0,sizeof(dp));
56         memset(use,false,sizeof(use));
57 
58         for(i=1;i<n;i++)
59         {
60             scanf("%d%d",&x,&y);
61             add(x,y);
62             add(y,x);
63         }
64         dfs(1);
65         hxl=20005;
66         for(i=1;i<=n;i++)
67         {
68             cur=Max(dp[i][0],n-dp[i][1]);
69             if(cur<hxl)
70             {
71                 hxl=cur;
72                 tom=i;
73             }
74         }
75         printf("%d %d\n",tom,hxl);
76     }
77     return 0;
78 }