POJ 1655 Balancing Act 樹形 DP：找重心並輸出最小最大分支大小

題目大意

多測資。每組給定 N 節點樹（N ≤ 20,000）。刪除某節點後，樹分裂為若干分支。定義該節點的**不平衡度** = 最大分支節點數。求**不平衡度最小**的節點（重心）及其不平衡度值。若多個節點同為最小，輸出編號最小者。

解法：樹形 DP 雙重 DFS（同 POJ 2378）

1. dfs1(u, fa)：計算 `sz[u]` = 以 `u` 為根的子樹大小。
2. dfs2(u, fa)：對每個 `u`，計算 `maxPart = max( 所有孩子 sz[v], N - sz[u] )`。
   維護全局 `bestVal`（最小不平衡度）和 `bestNode`（對應節點，取較小編號）。

完整 C++ 代碼（POJ AC 版）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 20005;
struct Edge { int to, next; } e[MAXN << 1];
int head[MAXN], ecnt;
int sz[MAXN];
int N, bestNode, bestVal;

void addEdge(int u, int v) {
    e[ecnt] = {v, head[u]};
    head[u] = ecnt++;
}

void dfs1(int u, int fa) {
    sz[u] = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == fa) continue;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int fa) {
    int maxPart = N - sz[u]; // 父側分支
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == fa) continue;
        dfs2(v, u);
        maxPart = max(maxPart, sz[v]); // 子樹分支
    }
    if (maxPart < bestVal || (maxPart == bestVal && u < bestNode)) {
        bestVal = maxPart;
        bestNode = u;
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        memset(head, -1, sizeof(int) * (N + 1));
        ecnt = 0;
        for (int i = 1; i < N; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            addEdge(a, b);
            addEdge(b, a);
        }
        bestVal = N;
        bestNode = N;
        dfs1(1, 0);
        dfs2(1, 0);
        printf("%d %d\n", bestNode, bestVal);
    }
    return 0;
}

測試數據

1
7
2 6
1 2
1 4
4 5
3 7
3 1

輸出：`1 3`（節點 1 為重心，最大分支大小 3）。

與 POJ 2378 差異對照

核心不變量：重心定義

樹的重心 = 刪除後**最大連通分量節點數最小**的節點。
性質：
1. 樹最多有 2 個重心，且相鄰。
2. 重心的不平衡度 ≤ N/2。
3. 可用「任意節點向最大子樹方向走」貪心找到重心（O(N) 單遍歷），但雙重 DFS 更直觀易寫。

遞歸棧安全建議

POJ 1655 N ≤ 20,000，遞歸深度極限情況（鏈狀樹）可能接近系統棧限制（Linux 預設 8MB，每幀 ~32B，約 25萬幀，通常安全）。但為通用性，建議：
- 使用 `-Wl,--stack=268435456`（Windows/MinGW）
- 或改寫非遞歸版（參考 POJ 2378 解析）。