POJ 2378 Tree Cutting 樹形 DP：雙重 DFS 找重心（刪除後最大子樹 ≤ N/2 的節點）

題目大意

給定 N 節點樹（N ≤ 100,000）。刪除某節點後，樹分裂為若干子樹（分支）。若**最大分支節點數 ≤ N/2**，稱該刪除「叼爆」（即該節點為**樹的重心**）。求所有重心節點編號（遞增輸出），無則輸出 `NONE`。

樹形 DP 核心思想：雙重 DFS

1. 第一次 DFS（自底向上）：計算 `dp[u]` = 以 `u` 為根的子樹節點數（含 `u`）。
2. 第二次 DFS（自頂向下）：對每個節點 `u`，計算刪除 `u` 後的最大分支大小：
   ‑ 子樹分支：`dp[v]`（`v` 為 `u` 的孩子）
   ‑ 父側分支：`N - dp[u]`
   取最大值 `maxPart`，若 `maxPart ≤ N/2` 則 `u` 為重心。

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

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

const int MAXN = 110000;
struct Edge { int to, next; } e[MAXN << 1];
int head[MAXN], ecnt;
int dp[MAXN], ans[MAXN], acnt;
int N;

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

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

void dfs2(int u, int fa) {
    int maxPart = 0;
    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, dp[v]); // 子樹分支
    }
    maxPart = max(maxPart, N - dp[u]); // 父側分支
    if (maxPart <= N / 2) ans[acnt++] = u;
}

int main() {
    while (scanf("%d", &N) == 1) {
        memset(head, -1, sizeof(int) * (N + 1));
        ecnt = acnt = 0;
        for (int i = 1; i < N; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            addEdge(a, b);
            addEdge(b, a);
        }
        dfs1(1, 0);
        dfs2(1, 0);
        sort(ans, ans + acnt);
        if (acnt == 0) puts("NONE");
        else for (int i = 0; i < acnt; i++) printf("%d\n", ans[i]);
    }
    return 0;
}

測試數據

10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8

輸出：`3` 和 `8`（兩個重心）。

關鍵點解析

複雜度

• 時間：O(N) 兩次 DFS + O(N log N) 排序（重心極少，實際 O(N)）。
• 空間：O(N) 邊表、dp、ans。

遞歸棧溢位解決方案（C++）

// 方法 1：手動棧模擬 dfs1
void dfs1_iter(int root) {
    static int stk[MAXN], top, fa[MAXN], state[MAXN];
    top = 0;
    stk[top++] = root;
    fa[root] = 0;
    while (top) {
        int u = stk[top - 1];
        if (state[u] == 0) { // 首次訪問
            state[u] = 1;
            dp[u] = 1;
            for (int i = head[u]; ~i; i = e[i].next) {
                int v = e[i].to;
                if (v == fa[u]) continue;
                fa[v] = u;
                stk[top++] = v;
            }
        } else { // 子樹已處理完，回溯
            top--;
            if (fa[u]) dp[fa[u]] += dp[u];
        }
    }
}

延伸：POJ 1655 Balancing Act

同樣是樹形 DP 找重心，但輸出**重心編號**與**最大分支大小的最小值**。代碼幾乎相同，僅 `dfs2` 中記錄 `minMaxPart` 對應節點。