POJ1655

Posted on | In ,

Balancing Act

Solution sketch

在樹上做DP，基本上是挑一個點當作 root 開始 DFS。維護 連同節點$u$在內已經拜訪過的子樹結點總數 和 拔掉節點$u$後最大的子數大小，就可以求出答案。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
vector<int> g[22222];
void add_edge(int u, int v)
{
    g[u].push_back(v);
    g[v].push_back(u);
}
bool seen[22222];
int mx_size[22222], num[22222];
int n;
void dfs(int u, int p)
{
    if (seen[u])
        return;
    seen[u] = true;
    num[u] = 1; // base case, see line 33
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == p)
            continue;
        dfs(v, u);
        mx_size[u] =
            max(mx_size[u], num[v]); // the subtree size below the current node u
        num[u] += num[v]; // the nodes visited so far under the current node u (including u itself)
    }
    mx_size[u] = max(mx_size[u], n - num[u]); // the "subtree" above the current node u under current traversal sequence
}
int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        scanf("%d", &n);
        for (int i = 0; i <= n; i++)
            g[i].clear();
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            add_edge(u, v);
        }
        memset(seen, false, sizeof(seen));
        memset(mx_size, 0, sizeof(mx_size));
        memset(num, 0, sizeof(num));
        dfs(1, -1);
        int mn = 22222, idx = 0;
        for (int i = 1; i <= n; i++) {
            if (mn > mx_size[i]) {
                idx = i;
                mn = min(mn, mx_size[i]);
            }
            // printf("%d %d\n", i, mx_size[i]);
        }
        printf("%d %d\n", idx, mn);
    }
    return 0;
}