POJ 3107 Godfather：樹形 DP 尋找重心（黑幫教父）

題目描述

給定無向樹（n ≤ 50000），刪除某節點後，剩餘連通塊最大尺寸最小的節點為「教父」。輸出所有教父節點編號（升序）。

解題思路：樹形 DP 計算子樹大小與最大連通塊

1. 任選根（如 1）DFS，計算每節點子樹大小 sz[u]。
2. 對於節點 u，刪除後連通塊為：各子樹、以及父方部分（大小 n - sz[u]）。最大連通塊大小 maxPart[u] = max(n - sz[u], max{sz[v] | v 為 u 子節點})。
3. 遍歷所有節點，找 minMaxPart，輸出對應節點。

C++ 代碼實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50010;
vector g[MAXN];
int sz[MAXN], maxPart[MAXN];
int n, minVal = INT_MAX;

void dfs(int u, int p) {
    sz[u] = 1;
    int mx = 0;
    for (int v : g[u]) if (v != p) {
        dfs(v, u);
        sz[u] += sz[v];
        mx = max(mx, sz[v]);
    }
    mx = max(mx, n - sz[u]); // 父方部分
    maxPart[u] = mx;
    minVal = min(minVal, mx);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int a, b; scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 0);
    bool first = true;
    for (int i = 1; i <= n; ++i)
        if (maxPart[i] == minVal) {
            if (!first) printf(" ");
            first = false;
            printf("%d", i);
        }
    printf("\n");
    return 0;
}

複雜度

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