HDU 1561 The more, The Better：樹形 DP 分組背包選節點最大權值

HDU 1561「The more, The Better」：樹上每節點有權值，選恰好 M 個節點（含根節點 0），要求選子節點必須選其父節點（即選擇集合為根向下封閉）。求最大權值和。本文解析樹形 DP + 分組背包模板。

問題建模

• 樹根為 0（虛擬根，權值 0），實際節點 1..N 掛在根下。
• 選 M+1 個節點（含根 0），即實際選 M 個非根節點。
• 父子依賴：選 v ⇒ 必選 parent[v]。
• 等價：每個節點可選或不選，但不選則其整棵子樹都不能選。

DP 狀態定義

dp[u][k] = 以 u 為根的子樹中，選 k 個節點（含 u）的最大權值。
若不選 u，則 k=0，值為 0（但狀態定義要求含 u，所以 k≥1）。

分組背包轉移

對節點 u，初始 dp[u][1] = val[u]（只選自己）。
遍歷孩子 v，合併 v 的子樹：

for k = 當前可選上限 .. 1:
    for t = 1 .. min(k-1, v子樹大小):
        dp[u][k] = max(dp[u][k], dp[u][k-t] + dp[v][t])

含義：從 u 現有選 k-t 個，再從 v 子樹選 t 個（v 必選，因 dp[v][t] 定義含 v）。

遞歸實現

int dfs(int u, int limit) { // limit = 剩餘可選配額
    int total = 0; // 子樹總節點數
    for (int v : children[u]) {
        int sz = dfs(v, limit - 1); // v 子樹大小
        total += sz;
        for (int k = min(limit, total); k >= 1; --k) {
            for (int t = 1; t <= sz && t <= k; ++t) {
                dp[u][k] = max(dp[u][k], dp[u][k-t] + dp[v][t]);
            }
        }
    }
    // 選 u 自己
    for (int k = min(total, limit); k >= 0; --k)
        dp[u][k+1] = dp[u][k] + val[u];
    return total + 1;
}

完整代碼（C++）

#include 
#include 
#include 
using namespace std;

const int MAXN = 210;
vector children[MAXN];
int dp[MAXN][MAXN];
int val[MAXN];
int N, M;

int dfs(int u, int limit) {
    int total = 0;
    for (int v : children[u]) {
        int sz = dfs(v, limit - 1);
        total += sz;
        for (int k = min(limit, total); k >= 1; --k) {
            for (int t = 1; t <= sz && t <= k; ++t) {
                dp[u][k] = max(dp[u][k], dp[u][k-t] + dp[v][t]);
            }
        }
    }
    for (int k = min(total, limit); k >= 0; --k)
        dp[u][k+1] = dp[u][k] + val[u];
    return total + 1;
}

int main() {
    while (scanf("%d%d", &N, &M) == 2 && (N || M)) {
        for (int i = 0; i <= N; ++i) children[i].clear();
        memset(val, 0, sizeof(val));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= N; ++i) {
            int p, v; scanf("%d%d", &p, &v);
            children[p].push_back(i);
            val[i] = v;
        }
        dfs(0, M+1); // 根 0 必選，共選 M+1 個
        printf("%d\n", dp[0][M+1]);
    }
    return 0;
}

複雜度

• N ≤ 200, M ≤ 200。
• 每條邊處理一次分組背包合併：O(N × M²) 最壞 8×10⁶，實際較小。
• 空間：O(N × M) ≈ 40KB。

關鍵細節

1. 虛擬根 0：權值 0，統一處理「必選根」約束。
2. 選 M+1 個：含根 0，實際業務選 M 個。
3. 分組背包逆序 k：避免重複使用同一孩子貢獻。
4. dp[u][k] 定義含 u：合併時 v 必選，符合父子依賴。
5. limit 參數：剪枝，避免超過總配額的無效計算。

總結

本題是「樹上選點、父子依賴、固定選取數量、最大化權值」的標準樹形 DP + 分組背包模板。核心模式：

1. 狀態 dp[u][k]：子樹選 k 個（含 u）最大值。
2. 初始 dp[u][1] = val[u]。
3. 孩子合併：雙層循環 k 逆序、t 正序，dp[u][k] = max(dp[u][k], dp[u][k-t] + dp[v][t])。
4. 最後補上 u 自身權值（或初始化時已含）。

此模板適用於所有「樹上帶依賴約束的固定基數選擇優化」問題。