POJ 1655 - Balancing Act

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

概要

ノード数 N の木が与えられる．

木から1つのノードを削除すると森，すなわちいくつかの木の集合となる． ノード n を削除したときに生じる木のサイズの最大値を「ノード n の balance」と呼ぶ．

balance の最小値と，その最小値を与えるノードを出力する．

制約

解法

POJ 3107 - Godfather と同じ．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 static const int M = 20000;
 5 
 6 int ans;
 7 int ans_min = M;
 8 
 9 int dfs(const pair<int,int> *edges, const int *begins, int N, int n, int parent)
10 {
11   int c = 1;
12   int m = 0;
13   for (int i = begins[n]; i < begins[n+1]; i++) {
14     const int *it = &edges[i].second;
15     if (*it != parent) {
16       const int x = dfs(edges, begins, N, *it, n);
17       c += x;
18       m = max(m, x);
19     }
20   }
21   m = max(m, N - c);
22   if (ans_min == m) {
23     ans = min(ans, n);
24   } else if (m < ans_min) {
25     ans_min = m;
26     ans = n;
27   }
28   return c;
29 }
30 
31 int main()
32 {
33   int T;
34   scanf("%d", &T);
35   while (T-- > 0) {
36     int N;
37     scanf("%d", &N);
38     static pair<int,int> edges[2*M];
39     for (int i = 0; i < N-1; i++) {
40       int u, v;
41       scanf("%d %d", &u, &v);
42       --u;  --v;
43       edges[2*i].first = edges[2*i+1].second = u;
44       edges[2*i].second = edges[2*i+1].first = v;
45     }
46     sort(edges, edges+2*(N-1));
47     static int begins[M];
48     begins[edges[0].first] = 0;
49     for (int i = 1; i < 2*(N-1); i++) {
50       if (edges[i].first != edges[i-1].first) {
51         begins[edges[i].first] = i;
52       }
53     }
54     begins[N] = 2*(N-1);
55 
56     ans = N;
57     ans_min = N;
58     dfs(edges, begins, N, 0, -1);
59     printf("%d %d\n", ans+1, ans_min);
60   }
61   return 0;
62 }
poj/1655.cc