最典型的树上背包代码：

#include <bits/stdc++.h>
#define endl '\n'
#define fst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
using ll = long long;

const int N = 105;
const int M = 1005;
const ll INF = -(1LL << 60);

int n, m;
vector<int> mp[N];
int v[N], w[N];
ll dp[N][M];
int siz[N];

void dfs(int u) {
    for (int j = 0; j <= m; j++) dp[u][j] = INF;

    if (v[u] <= m) dp[u][v[u]] = w[u];
    siz[u] = v[u];

    for (int son : mp[u]) {
        dfs(son);

        for (int j = min(m, siz[u] + siz[son]); j >= v[u]; j--) {
            for (int k = 1; k <= min(siz[son], j - v[u]); k++) {
                if (dp[u][j - k] == INF || dp[son][k] == INF) continue;
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
            }
        }

        siz[u] = min(m, siz[u] + siz[son]);
    }
}

signed main() {
    fst;

    cin >> n >> m;

    for (int i = 2; i <= n; i++) {
        int fa;
        cin >> fa;
        mp[fa].push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    dfs(1);

    ll ans = 0;
    for (int j = 0; j <= m; j++) ans = max(ans, dp[1][j]);

    cout << ans << endl;

    return 0;
}

---

先说这份代码到底在做什么

这份代码在解决：

• 每个点有体积 v[u]
• 每个点有价值 w[u]
• 背包容量是 m
• 如果选儿子，就必须选爸爸
• 求最大价值

---

第一部分：变量都是什么

1.

int n, m;

• n = 一共有多少个点
• m = 背包容量

---

2.

vector<int> mp[N];

这个是“树”。

比如 mp[2] 里面放的是：

• 2 的所有儿子

你可以把它理解成：

• mp[u] = u 下面连着谁

---

3.

int v[N], w[N];

• v[u] = 第 u 个点的体积
• w[u] = 第 u 个点的价值

---

4.

ll dp[N][M];

这个最重要。

dp[u][j] 的意思是：

在 u 这棵子树里，已经选了 u，并且总共用了 j 的容量，最多能拿多少价值

你先死记这一句都行。

---

5.

int siz[N];

这个不是结点个数。

这里它表示的是：

• 当前 u 这棵子树，最多可能用到多少容量

它只是为了让循环少跑一点，更快。

---

第二部分：dfs 在干什么

这一句

void dfs(int u)

表示：

• 现在开始处理结点 u
• 顺便把 u 的整棵子树都算出来

---

第三部分：初始化

这一段

for (int j = 0; j <= m; j++) dp[u][j] = INF;

意思是：

• 先把 u 的所有状态都设成“不能做到”

因为一开始还没开始选，所以默认都不合法。

这里的 INF 是个特别小的负数，表示：

• 这个状态不存在
• 不要拿它来更新答案

---

这一句

if (v[u] <= m) dp[u][v[u]] = w[u];

这是最关键的初始化。

意思是：

• 如果只选 u 自己
• 那么会占用 v[u] 的容量
• 得到 w[u] 的价值

所以：

dp[u][v[u]] = w[u];

比如：

• u 的体积是 3
• u 的价值是 8

那就是：

• 用 3 格容量
• 得到 8 分

---

这一句

siz[u] = v[u];

表示：

• 现在还只选了自己
• 所以当前最多只会用到 v[u] 这么多容量

---

第四部分：处理儿子

这一段

for (int son : mp[u]) {
    dfs(son);

意思是：

• 先把 u 的每个儿子 son 的答案都算出来
• 因为要先知道孩子能提供什么，爸爸才知道怎么选

这就像：

• 先知道每个小朋友手里有几块糖
• 再决定怎么分给大家

---

第五部分：最难的转移

这段最容易看不懂：

for (int j = min(m, siz[u] + siz[son]); j >= v[u]; j--) {
    for (int k = 1; k <= min(siz[son], j - v[u]); k++) {
        if (dp[u][j - k] == INF || dp[son][k] == INF) continue;
        dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
    }
}

我拆开讲。

---

外层 j 是什么

for (int j = ...)

j 表示：

• 当前想让 u 这棵树总共用 j 的容量

比如：

• 现在我们想试试“总容量用 7 格时，最好是多少价值”

那就对应某个 j=7

---

内层 k 是什么

for (int k = ...)

k 表示：

• 分给儿子 son 这棵子树多少容量

也就是说：

• 总共要用 j
• 其中拿出 k 给儿子
• 剩下的 j-k 留给原来已经处理好的部分

---

这一句最核心

dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);

意思是：

现在要凑出 “u 子树用了 j 容量” 的答案。

办法是：

• 原来已经处理好的部分，用了 j-k
• 儿子 son 那部分，用了 k
• 把两边价值加起来

然后看看是不是更优。

---

你可以把它想成“分书包空间”

比如现在书包总共能给 u 这棵树 8 格空间。

你在想：

• 给儿子 1 格，行不行？
• 给儿子 2 格，行不行？
• 给儿子 3 格，行不行？

每试一种分法，就更新一次。

这就是：

j 固定总容量
k 枚举分给儿子的容量

---

为什么 k 从 1 开始，不从 0 开始？

因为这份代码的定义是：

• dp[son][k] 表示已经选了 son
• 如果你要从儿子这边拿东西，就至少得把儿子自己选上
• 所以容量至少是 1 个合法状态，不会是 0

而“不选这个儿子”这件事，其实已经被保存在 dp[u][j] 原来的值里了。

也就是说：

• 不选儿子：啥也不做
• 选儿子：枚举 k >= 1

---

为什么 j 要倒着循环？

for (int j = ...; j >= ...; j--)

因为这是背包合并。

倒着枚举是为了防止：

• 同一个儿子被重复算很多次

你现在先简单记住：

这种背包合并，外层容量通常倒着枚举。

---

这一句是在防止出错

if (dp[u][j - k] == INF || dp[son][k] == INF) continue;

意思是：

如果这两种状态本来就不存在，那就跳过。

比如：

• u 原来的状态凑不出来
• 或者儿子用 k 容量的状态凑不出来

那当然不能拿来相加。

---

这一句是更新范围

siz[u] = min(m, siz[u] + siz[son]);

意思是：

• 现在把儿子并进来了
• 所以 u 这棵子树能用的最大容量变大了

原来最多 siz[u] 加上儿子最多 siz[son] 所以更新一下。

但不能超过背包总容量 m

---

第六部分：主函数

读入

cin >> n >> m;

输入点数和背包容量。

---

建树

for (int i = 2; i <= n; i++) {
    int fa;
    cin >> fa;
    mp[fa].push_back(i);
}

意思是：

• 2 到 n 这些点，每个点都有一个爸爸
• 把它挂到爸爸下面

比如输入 fa=1，就表示：

• 这个点是 1 的儿子

---

读每个点的体积和价值

for (int i = 1; i <= n; i++) {
    cin >> v[i] >> w[i];
}

---

从根开始算

dfs(1);

因为这棵树的根是 1，所以从 1 开始处理整棵树。

---

最后找答案

ll ans = 0;
for (int j = 0; j <= m; j++) ans = max(ans, dp[1][j]);

意思是：

• 根这棵树里
• 容量只要不超过 m
• 哪个价值最大就取哪个

---

最后我用一句最简单的话总结这份代码

这份代码做的事就是：

1. 每个点先只选自己
2. 再一个一个把儿子合并进来
3. 合并时试试“分给儿子多少背包空间”
4. 最后算出根节点的最好答案

---

你最容易卡住的，其实只有这一句

一定要反复记：

dp[u][j]

不是“随便选”。

它的意思是：

在 u 的子树里，已经选了 u，总容量用 j 时，最大价值是多少

只要这句话你明白了，后面转移就是在做：

• 把孩子接进来
• 看怎么分容量更划算

---

我建议你这样学

你先不要一口气看完整份代码。

你可以按这个顺序理解：

第一步，只看这两句：

if (v[u] <= m) dp[u][v[u]] = w[u];
siz[u] = v[u];

先理解成：

• 每个点最开始只有“选自己”这一种情况

第二步，再看这句：

dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);

理解成：

• 把儿子的答案拼到爸爸身上

第三步，再去看整个双重循环。

---