HDU 1561 城堡攻略：树形背包 DP 选 M 个节点最大权值

题目大意

N 座城堡（N≤200）形成树结构（每城堡有一前置城堡，0 表示根）。每城堡有宝物价值。必须攻克恰好 M 个城堡（M≤N），且攻克某城堡需先攻克其父城堡。求最大宝物总价值。

树形背包 DP

• 加虚拟根 0，价值 0，连接所有原根
• dp[u][j]：以 u 为根的子树中选 j 个节点的最大价值
• 初始：dp[u][j] = val[u] (j≥1)
• 合并子树 v：dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]) for k=1..j-1
• 答案：dp[0][M+1]（含虚拟根，实际选 M 个）

C++ 实现

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 205;
struct Edge { int v, next; } edge[MAXN*2];
int head[MAXN], ecnt, n, m, dp[MAXN][MAXN], val[MAXN];

void addEdge(int u, int v) {
    edge[ecnt] = {v, head[u]};
    head[u] = ecnt++;
}

void dfs(int u) {
    for (int j = 1; j <= m+1; ++j) dp[u][j] = val[u];
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].v;
        dfs(v);
        for (int j = m+1; j >= 2; --j)
            for (int k = 1; k < j; ++k)
                dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
    }
}

int main() {
    while (scanf("%d%d", &n, &m) == 2 && (n||m)) {
        memset(head, -1, sizeof(head));
        ecnt = 0;
        val[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            addEdge(a, i);
            val[i] = b;
        }
        memset(dp, 0, sizeof(dp));
        dfs(0);
        printf("%d\n", dp[0][m+1]);
    }
    return 0;
}

关键细节

1. 虚拟根技巧：统一处理多棵树，答案取 dp[0][M+1]
2. 容量倒序：j 从大到小，保证 01 化（每个子树只能合并一次）
3. 初始化：dp[u][j]=val[u] 表示选 u 且不选子树任何节点

复杂度

• 时间：O(N·M²) = 200×200² = 8e6，极快
• 空间：O(N·M)

样例验证

3 2
0 1
0 2
0 3
→ 选价值 2,3 的城堡，和=5