poj 1655 Balancing Act 求树的重心

 1 //#include <bits/stdc++.h>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <vector>
 5 #include <cstring>
 6 using namespace std;
 7 int T, N;
 8 #define maxn 20010
 9 vector <int> mp[maxn];
10 int vis[maxn];
11 int sonSum[maxn], leftSum[maxn];
12 int sonMax[maxn], ans[maxn];
13 int find_son_co(int fa)
14 {
15     vis[fa] = 1; sonSum[fa] = 1;
16     bool flag = false;
17     for(int i = 0; i < mp[fa].size(); i++)
18     {
19         if(vis[mp[fa][i]]) continue;
20         flag = true;
21         int temp = find_son_co(mp[fa][i]);
22         if(temp >= sonMax[fa]) sonMax[fa] = temp;
23         sonSum[fa] += temp;
24     }
25     return sonSum[fa];
26 }
27 int main() 
28 {
29   //  freopen("in.txt", "r", stdin);
30     scanf("%d", &T);
31     while(T--)
32     {
33         scanf("%d", &N);
34         for(int i = 1; i <= N; i++) mp[i].clear();
35         for(int i = 1; i <= N-1; i++)
36         {
37             int a, b; scanf("%d%d", &a, &b);
38             mp[a].push_back(b);
39             mp[b].push_back(a);
40         }
41         memset(vis, 0, sizeof(vis));
42         memset(sonSum, 0, sizeof(sonSum));
43         memset(sonMax, 0, sizeof(sonMax));
44         find_son_co(1);
45         for(int i = 1; i <= N; i++)
46         {
47             leftSum[i] = N - sonSum[i];
48         }
49         int mmin = 0x3f3f3f3f; int pos;
50         for(int i = 1; i <= N; i++)
51         {
52             int temp = max(leftSum[i], sonMax[i]);
53             if(temp <= mmin)
54             {
55                 pos = i; mmin = temp;
56             }
57         }
58         printf("%d %d\n", pos, mmin);
59     }
60     return 0;
61 }