您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1655 樹形 DP：求每個節點作為根時的最大子樹大小

編輯：關於C++

POJ 1655 要求對一棵無根樹，對每個節點 u，計算以 u 為根時，所有子樹中最大子樹的節點數。這是經典的「換根 DP」/「樹形 DP 兩遍掃描」問題。

一、問題建模

輸入：n 個節點，n-1 條無向邊（保證成樹）。
輸出：對每個節點，輸出以其為根時，最大子樹大小的最小值（即該節點的「重心」指標）。
等價：對節點 u，刪除 u 後形成若干連通塊，最大連通塊的大小即為答案。

二、樹形 DP 兩階段法

第一遍 DFS：自底向上計算子樹大小

subtree[u] = 以 u 為根的子樹節點數（含 u）。
dp[u] = 以 u 為根時，子樹方向的最大子樹大小（即最大的直接子樹）。

void dfs1(int u, int parent) {
    subtree[u] = 1;
    dp[u] = 0;
    for (int v : adj[u]) if (v != parent) {
        dfs1(v, u);
        subtree[u] += subtree[v];
        dp[u] = max(dp[u], subtree[v]);
    }
}

第二遍 DFS：自頂向下傳遞父方向信息

對節點 u，其父方向連通塊大小 = n - subtree[u]。
最終答案 ans[u] = max(dp[u], n - subtree[u])。
但需將父方向信息正確傳給子節點：對子節點 v，其父方向最大塊 = max(n - subtree[v], 兄弟子樹最大值, 祖父方向值)。用「前綴最大/後綴最大」或「記錄最大/次大子樹」優化到 O(1) 轉移。

三、完整 AC 代碼（C++11，鄰接表 + 兩遍 DFS）

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

const int MAXN = 20010;
vector<int> adj[MAXN];
int n;
int subtree[MAXN];   // 子樹大小
int dp[MAXN];        // 子樹方向最大子樹
int ans[MAXN];       // 最終答案

void dfs1(int u, int p) {
    subtree[u] = 1;
    dp[u] = 0;
    for (int v : adj[u]) if (v != p) {
        dfs1(v, u);
        subtree[u] += subtree[v];
        dp[u] = max(dp[u], subtree[v]);
    }
}

void dfs2(int u, int p, int up_val) {
    // up_val 為父方向（含祖先及兄弟）的最大連通塊大小
    ans[u] = max(dp[u], up_val);
    
    // 預處理：找出最大、次大子樹，用於 O(1) 計算兄弟最大值
    int max1 = -1, max2 = -1, max1_id = -1;
    for (int v : adj[u]) if (v != p) {
        if (subtree[v] > max1) {
            max2 = max1;
            max1 = subtree[v];
            max1_id = v;
        } else if (subtree[v] > max2) {
            max2 = subtree[v];
        }
    }
    
    for (int v : adj[u]) if (v != p) {
        int sibling_max = (v == max1_id) ? max2 : max1;
        int new_up = max({up_val, sibling_max, n - subtree[v]});
        dfs2(v, u, new_up);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) adj[i].clear();
        for (int i = 0; i < n - 1; ++i) {
            int u, v; cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dfs1(1, 0);
        dfs2(1, 0, 0);
        
        int best = n;
        for (int i = 1; i <= n; ++i) best = min(best, ans[i]);
        // 題目通常要求輸出所有最優節點，或僅輸出最小值
        // 這裡輸出最小值及對應節點
        cout << best << '\n';
        // for (int i = 1; i <= n; ++i) if (ans[i] == best) cout << i << ' ';
        // cout << '\n';
    }
    return 0;
}