题意

$N$ 个物品构成一棵依赖树，选子节点必须先选父节点。每个物品有体积 $v_i$ 和价值 $w_i$，每种只有一件。背包容量 $V$，求最大总价值。

思路

一句话本质：必须先选父才能选子，依赖形成树形结构——对每个节点 $u$，$dp[u][j]$ 表示子树 $u$ 用 $j$ 容量的最大价值。先保证 $u$ 本身被选，再把每个子节点 c 的分配合并到 $dp[u]$ 中。

先看暴力：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50import sys


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    V = next(it)
    v = [0] * (N + 1)
    w = [0] * (N + 1)
    parent = [0] * (N + 1)
    for i in range(1, N + 1):
        v[i] = next(it)
        w[i] = next(it)
        parent[i] = next(it)

    ans = 0
    for mask in range(1 << N):
        selected = [False] * (N + 1)
        ok = True
        for i in range(N):
            if mask & (1 << i):
                selected[i + 1] = True
        for i in range(1, N + 1):
            if not selected[i]:
                continue
            p = parent[i]
            while p != -1:
                if not selected[p]:
                    ok = False
                    break
                p = parent[p]
            if not ok:
                break
        if not ok:
            continue
        vol = 0
        val = 0
        for i in range(1, N + 1):
            if selected[i]:
                vol += v[i]
                val += w[i]
        if vol <= V:
            ans = max(ans, val)

    print(ans)


if __name__ == '__main__':
    solve()

暴力枚举所有 $2^N$ 种选择方案，用父节点链检查依赖合法性。$O(2^N)$ 在 $N=100$ 时不可行。

依赖是树形的，怎么用 DP？

假设我们以节点 $u$ 为根。如果选 $u$，则可以选 $u$ 的任意子节点（及其后代）；如果不选 $u$，则 $u$ 的所有后代都不能选。这提示我们自底向上做树形 DP：从叶子开始，把子树的 DP 结果合并到父节点上。

dp[u][j] 的含义是什么？

定义 $dp[u][j]$：以 $u$ 为根的子树，在占用容量 $j$ 时能获得的最大价值。这个定义隐含了一个约束：$u$ 必须被选。因为如果 $u$ 不被选，整棵子树都不能选，dp 值就是 0。

怎么初始化 dp[u]？

首先把 $u$ 本身的体积和价值放入 DP 状态。对 $j \ge v_u$：$dp[u][j] = w_u$（只选 $u$ 自己，不选任何后代）。对 $j < v_u$：$dp[u][j] = 0$（容量不够，连 $u$ 自己都装不下）。

怎么把子节点 c 合并到 u 上？

处理完子节点 $c$ 的 DFS 后，$dp[c][\cdot]$ 已经计算完毕。现在要把子树的贡献合并到 $dp[u]$ 上。

对于一个容量为 $j$ 的背包（分配给 $u$ 的子树），可以把一部分容量 $k$ 分给子树 $c$，剩余 $j - k$ 留给 $u$ 和其他已处理过的子节点。转移方程：

这里 $j$ 从 $V$ 倒序到 $v_u$（因为 $u$ 必须至少占 $v_u$），$k$ 从 $0$ 到 $j - v_u$。

这个合并和分组背包有什么关系？

每个子节点 $c$ 对 $dp[u]$ 的贡献，本质上是一次"容量分配"的决策：给子树 $c$ 分多少容量（$k$ 可以是 0 到 $j - v_u$）。这和分组背包中"每组选 0 或 1 个"类似——只不过不是选物品，而是选分配量。

因此合并每个子节点时，需要用到分组背包的"旧状态隔离"思想：dp[u][j - k] 应该来自处理当前子节点之前的旧状态，而不是被当前子节点反复更新的新状态。所以 $j$ 必须是倒序，以保证用到的 dp[u][j - k] 是上一轮（上一个子节点合并后）的状态。

为什么要引入虚拟根 0？

题面中 $p_i = -1$ 表示根节点。一棵森林中有可能存在多棵独立的依赖树。引入虚拟根 $0$（体积 0、价值 0），让所有 $p_i = -1$ 的节点挂在这棵虚拟根下，DP 只从根 0 开始一次 DFS 即可。最终答案就是 $dp[0][V]$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
int N, V;
int v[maxn], w[maxn];          // 每个节点的体积和价值
vector<int> children[maxn];    // 树形依赖关系
// dp[u][j] 表示以 u 为根的子树，占用容量 j 时的最大价值。
int dp[maxn][maxn];

void dfs(int u) {
    // 先把节点 u 本身的价值放入（必须选 u 才能选其子节点）。
    for (int j = v[u]; j <= V; j++)
        dp[u][j] = w[u];
    for (int c : children[u]) {
        dfs(c);
        // 给子节点分配容量，类似分组背包：子节点只能选一个「分配量」。
        for (int j = V; j >= v[u]; j--)
            for (int k = 0; k <= j - v[u]; k++)
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[c][k]);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1) {                   // 根节点挂在虚拟根 0 下
            children[0].push_back(i);
        } else {
            children[p].push_back(i);
        }
    }
    dfs(0);
    cout << dp[0][V] << '\n';
    return 0;
}

复杂度

时间 $O(N \times V^2)$。每个节点的子节点合并需要两重循环（容量 $V$ 和分配量 $k$），最坏情况下 $N$ 个节点，总复杂度 $O(NV^2)$。$N, V \le 100$ 时约 $10^6$，可以通过。

空间 $O(NV)$，需要 $N \times (V+1)$ 的二维 DP 数组。

总结

有依赖的背包是"树形 DP + 背包容量分配"的结合。核心是两点：先保证根节点被选（$dp[u][j \ge v_u] = w_u$），再把每个子节点的子树 DP 以容量分配的方式分组合并到父节点上。这种"在子节点上分配容量"的思想，也是更复杂的树形背包问题的基础。