HDU 1561 The more, The Better：樹形 DP + 依賴背包詳解

問題建模

• N 座城堡（節點），每座有寶物值 val[i]。
• 依賴關係構成一棵有根樹：攻克 i 必須先攻克 parent[i]（parent[i]=0 為根）。
• 最多攻克 M 座城堡，求最大寶物總值。

這正是樹上的依賴背包問題：選擇子節點必須先選擇父節點。

狀態定義

dp[u][k]：以 u 為根的子樹中，選擇 k 個節點（含 u）的最大收益。
關鍵約束：若選擇 u 的某個後代，則 u 必須被選擇。

轉移方程：組合子樹背包

對節點 u，初始 dp[u][1] = val[u]（只選自己）。
遍歷每個子節點 v，將 v 的子樹作為一組物品合併到 u 的背包中：

for (int v : children[u]) {
    dfs(v);  // 先算好子樹 dp
    for (int j = cur_max; j >= 1; --j)      // 逆序遍歷容量（01 背包）
        for (int k = 1; k <= min(j-1, sz[v]); ++k)  // 從 v 子樹選 k 個
            dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
}

注意：j-k ≥ 1 保證 u 被選中；k=0 對應不選 v 子樹，已隱含在 dp[u][j] 原值中。

虛擬根節點技巧

原題允許攻克多棵獨立的樹（多個 parent=0）。引入 虛擬根 0，val[0]=0，所有 parent=0 的節點掛在 0 下。最終答案為 dp[0][M+1]（+1 計入虛擬根）。

完整代碼（優化版）

#include 
using namespace std;
const int MAXN = 205;
int n, m, val[MAXN], dp[MAXN][MAXN], sz[MAXN];
vector g[MAXN];

void dfs(int u) {
    dp[u][1] = val[u];
    sz[u] = 1;
    for (int v : g[u]) {
        dfs(v);
        for (int j = sz[u] + sz[v]; j >= 1; --j) {
            for (int k = 1; k <= min(sz[v], j-1); ++k)
                dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
        }
        sz[u] += sz[v];
    }
}

int main() {
    while (cin >> n >> m, n || m) {
        for (int i = 0; i <= n; ++i) {
            g[i].clear();
            fill(dp[i], dp[i]+m+2, 0);
        }
        for (int i = 1; i <= n; ++i) {
            int p; cin >> p >> val[i];
            g[p].push_back(i);
        }
        dfs(0);
        cout << dp[0][m+1] << endl;
    }
    return 0;
}

複雜度分析

• 狀態數：O(N × M)，N, M ≤ 200。
• 轉移：每條邊做一次背包合併，總時間 O(N × M²) ≈ 8×10⁶，極快。
• 空間：dp[205][205] 約 160 KB。

核心心得

1. 依賴背包 = 分組背包：父節點與其子樹形成一組，必選父節點，子樹可選可不選。
2. DFS 後序：必須先算完子樹再合併父節點。
3. 虛擬根：統一處理多棵獨立樹，簡化邏輯。
4. 逆序遍歷容量：保證 01 背包性質，避免重複使用同一子樹。