POJ 2378 Tree Cutting：判斷樹的所有重心節點

問題差異

與 POJ 1655 不同：本題要求輸出**所有**滿足條件的節點（最大分支 ≤ N/2），按編號升序，無則輸出 NONE。這就是找出樹的**所有重心** (1個或2個相鄰節點)。

算法邏輯

完全復用 POJ 1655 的雙 DFS 模板，僅修改答案收集邏輯：

void dfs2(int u, int p) {
    int mx = N - sz[u];
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == p) continue;
        dfs2(v, u);
        mx = max(mx, sz[v]);
    }
    if (mx <= N/2) ans[++cnt] = u;  // 收集所有符合條件節點
}

完整代碼

#include 
#include 
#include 
using namespace std;

const int MAXN = 110000;
struct Edge { int to, next; } e[MAXN*2];
int head[MAXN], ecnt;
int sz[MAXN], N, ans[MAXN], cnt;

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

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

void dfs2(int u, int p) {
    int mx = N - sz[u];
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == p) continue;
        dfs2(v, u);
        mx = max(mx, sz[v]);
    }
    if (mx <= N/2) ans[++cnt] = u;
}

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

數學性質：重心最多兩個且相鄰

• 若 N 為奇數：唯一重心
• 若 N 為偶數：可能有兩個相鄰重心 (刪除它們的連邊，得到兩個大小 N/2 的子樹)
• 證明：假設有三個重心，取其中兩個最遠，路徑中點分支大小會超過 N/2，矛盾

測試用例

輸入:
10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8

輸出:
3
8
// 兩個重心，刪除任意一個，最大分支=5 (N/2)

避坑指南

1. 多測試用例：`while (scanf("%d", &N) == 1)` 讀到 EOF 結束
2. 數組大小：邊數 2*(N-1)，開 `MAXN*2`
3. 遞歸深度：N=100000 可能棧溢出，競賽常加 `#pragma comment(linker, "/STACK:1024000")` (MSVC) 或改迭代 DFS
4. 輸出格式：每行一個編號，無則 `NONE`，注意大小寫

總結

POJ 2378 是 POJ 1655 的直接變體，核心同為**樹形 DP 換根思想**。區別在於答案收集邏輯：單一最優 vs 所有滿足條件。理解「重心 ≤ N/2」的等價定義，掌握雙 DFS 模板，此類問題秒殺。建議將模板封裝為通用「樹重心查找器」，復用於 LUOGU P2016、Codeforces 等同類題目。