POJ 3107 Godfather：樹形 DP 尋找最小最大連通分量

問題大意

給定 n 個節點的樹（n ≤ 50,000），刪除一個節點後樹分裂為多個連通塊。Godfather 定義為刪除後最大連通塊節點數最小的節點。求所有符合條件的節點並升序輸出。

樹形 DP 分析

刪除節點 u 後，連通塊包括：

• 每個子樹 dp[v]（v 為 u 的孩子）。
• 父親方向的塊：n - dp[u]。

最大塊大小為 max(n - dp[u], max(dp[v]))。DFS 計算所有 dp[u]，再遍歷求最小最大值。

代碼實現

void dfs(int u, int fa) {
    dp[u] = 1;
    for (auto e = head[u]; e; e = e->next) {
        int v = e->v;
        if (v == fa) continue;
        dfs(v, u);
        dp[u] += dp[v];
    }
}

void solve(int u, int fa) {
    int maxPart = n - dp[u]; // 父方向
    for (auto e = head[u]; e; e = e->next) {
        int v = e->v;
        if (v == fa) continue;
        solve(v, u);
        maxPart = max(maxPart, dp[v]);
    }
    if (maxPart < ans) { ans = maxPart; res.clear(); res.push_back(u); }
    else if (maxPart == ans) res.push_back(u);
}

複雜度

兩次 DFS，時間 O(n)，空間 O(n)，滿足 n=50,000 限制。