POJ 3107 - Godfather

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

概要

n 人のマフィア関係者の関係が無向木として表されている．

Godfather は，木のルートであり，そのノードを消したときに残った連続成分の最大のサイズが最小になるという性質を持っている．

Godfather でありうるノードの番号をすべて出力する．

制約

• 2 <= n <= 50000

解法

適当なノードを木のルートに設定して，DFS で各ノードをルートとする部分木のサイズ s[1], ..., s[k] を求める． すると，そのノードを消したときの連続成分のサイズは s[1], ..., s[k], n - Σs[i] なので，これの最大値が最小になるようなノードを列挙すればいい．

n <= 50000 なので余裕のように見えるけど，普通に隣接リストで木を表現して DFS だと TLE…

木をエッジのリストで表現して同じように DFS したら通った (704MS)．

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