POJ 3107 Godfather (树重心)

题意:
数重心，并按从小到大输出。
思路:
dfs
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 const int N = 5e4 + 5;
 7 struct Edge {
 8     int next, to;
 9 }edge[N << 1];
10 vector <int> G[N];
11 int dp[N], n, head[N], cnt;
12 
13 inline void add(int u, int v) {
14     edge[cnt].next = head[u];
15     edge[cnt].to = v;
16     head[u] = cnt++;
17 }
18 
19 int dfs(int u, int p) {
20     dp[u] = 0;
21     int sum = 0;
22     for(int i = head[u]; ~i; i = edge[i].next) {
23         int v = edge[i].to;
24         if(v == p)
25             continue;
26         int temp = dfs(v, u);
27         dp[u] = max(dp[u], temp);
28         sum += temp;
29     }
30     dp[u] = max(dp[u], n - sum - 1);
31     return sum + 1;
32 }
33 
34 int main()
35 {
36     while(~scanf("%d", &n)) {
37         for(int i = 1; i <= n; ++i) {
38             head[i] = -1;
39         }
40         cnt = 0;
41         for(int i = 1; i < n; ++i) {
42             int u, v;
43             scanf("%d %d", &u, &v);
44             add(u, v);
45             add(v, u);
46         }
47         dfs(1, -1);
48         int Max = n;
49         vector <int> ans;
50         for(int i = 1; i <= n; ++i) {
51             Max = min(Max, dp[i]);
52         }
53         for(int i = 1; i <= n; ++i) {
54             if(Max == dp[i]) {
55                 ans.push_back(i);
56             }
57         }
58         for(int i = 0; i < ans.size(); ++i) {
59             if(i == ans.size() - 1) {
60                 printf("%d
", ans[i]);
61             } else {
62                 printf("%d ", ans[i]);
63             }
64         }
65     }
66     return 0;
67 }