POJ 1655 Balancing Act：樹的重心 O(n) 求解

題目大意

給定一棵樹，找到重心：移除該點後，剩餘各連通塊（子樹）中最大節點數最小。輸出重心編號及該最大子樹大小。

樹形 DP 遞推

• sz[u]：以 u 為根的子樹大小。
• 對每個節點 u，其移除後產生的塊大小為：
  所有子樹 sz[v]，以及「父方向」塊 n - sz[u]。
  該點的平衡值 = max( max_child_sz, n - sz[u] )。
• DFS 一次計算所有 sz 並更新全局最小平衡值對應的節點。

完整代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20010, INF = 0x3f3f3f3f;
struct Edge { int v, nxt; } e[MAXN<<1];
int h[MAXN], ec, n, ans, minBal;
int sz[MAXN];

void addEdge(int u, int v) {
    e[ec] = {v, h[u]}; h[u] = ec++;
}
void init() { fill(h, h+n+1, -1); ec = 0; minBal = INF; }
void dfs(int u, int fa) {
    sz[u] = 1; int mx = 0;
    for (int i = h[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
        mx = max(mx, sz[v]);
    }
    mx = max(mx, n - sz[u]);  // 父方向塊
    if (mx < minBal) { minBal = mx; ans = u; }
}
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        init();
        for (int i = 1, u, v; i < n; ++i) {
            scanf("%d%d", &u, &v);
            addEdge(u, v); addEdge(v, u);
        }
        dfs(1, 0);
        printf("%d %d\n", ans, minBal);
    }
    return 0;
}

複雜度

• 時間：O(n)，單次 DFS。
• 空間：O(n)。

關鍵點

1. 遞歸計算子樹大小，同時評估每個節點的平衡值。
2. 父方向塊大小 = n - sz[u]，易漏。
3. 樹不一定以 1 為根，但 DFS 從任意節點開始結果相同。
4. 若有多個重心（平衡值相同），題目通常要求輸出編號最小者（代碼中 < 保證首個最小）。