$\LARGE\color{orange}{刷题日记(算法提高课)}$

回顾线性背包的定义：考虑前 $i$ 个物品，在体积不超过 $j$ 下的最大价值

这里树型背包的定义改为：考虑以节点 $u$ 为根的子树，在体积不超过 $j$ 下的最大价值

在线性背包的定义中，$f[i]$ 的状态只需要通过 $f[i-1]$ 的状态便可以轻易求出

在树型背包中，$f[u]$ 的状态需要由各个子树转移过来，设子树的编号为 $son_i$ ，我们发现二者之间不再是简单的线性关系

我们先按照线性背包的角度来考虑树型背包：

如果不选节点 $u$ ，由于本题的限制，所有的子节点都不能选，因此 $f[u][j]=0$

如果选择节点 $u$ ，此时剩余体积为 $j-v[u]$

不难发现，我们可以轻易地通过遍历各个子节点来用 $son_i$ 来表示以子节点为根的子树，也就是数组的第一维，但数组的第二维我们无法表示出来，即以 $son_i$ 为根的子树所对应的体积无法确定

但有一个性质，如果当前以节点 $u$ 为根的子树的体积为 $j$ 的话，所有以 $son_i$ 为根的子树的体积相加一定等于 $j$

基于这一点，由于我们无法确定以节点 $son_i$ 为根的子树的体积为多大，因此我们考虑从 0 开始遍历，最大到 $j$

那么这便是一个分组背包问题了，「组」就是以节点 $son_i$ 为根的每个子树，我们从小到大遍历以 $son_i$ 为根节点的子树的体积

由于每个物品只能选取一个，因此本质上还是 01 背包，所有我们在体积 $j$ 的遍历上还是从后往前

在不同的体积 $j$ 的基础上，我们用 $k$ 表示每个组的体积，此时每个组的最大价值可以表示为 $f[son][k]$ ，那么 $f[u][j]$ 便可以通过 $f[u][j-k]$ 再加上 $f[son][k]$ 转移过来

由于在对以 $son_i$ 为根的子树考虑时，我们一定要选节点 $u$ ，因此我们需要预留一个位置给节点 $u$ ，即 $j$ 的遍历是从 $m-v[u]$ 开始的

当我们遍历完所有的以 $son_i$ 为根的子树时，我们需要将节点 $u$ 的价值加上，即所有体积大于等于 $v[u]$ 的状态均可以从 $f[u][j-v[u]]+w[u]$ 转移而来，小于的全部置 0 （因为如果不能选节点 $u$ ，那么其所有的孩子节点均不能选）

在遍历体积时，我们是从后往前遍历，关于这个我们详细说明一下：

我们 $f[u][j]$ 的定义为：考虑以 $u$ 为根的子树，在背包体积不超过 $j$ 的所有选法

实际上这里是省区了一维，完整写法应该是 $f[u][i][j]$ 的定义为：考虑以 $u$ 为根的子树，对以 $u$ 为根的前 $i$ 个子树进行选择，在背包体积不超过 $j$ 的所有选法

完整代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int f[N][N];
int h[N], e[N], ne[N], idx;
int v[N], w[N];
int n, m;

void dfs(int u)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int son = e[i];
        dfs(son);//先对当前子树遍历一次，之后再处理f[u][j]，这是因为我们的遍历方式是从下往上遍历的，即后序遍历
        for(int j = m - v[u]; j >= 0; j--)//提前预留第u个物品的体积，遍历 考虑范围相同 但 体积不同 下的情况
        {
            //由于每个物品只能用一次，因此是01背包，从后往前遍历
            for(int k = 0; k <= j; k++)//遍历每个子树的体积，不能超过j
            {
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);//每个子树的体积为k，那么只能从j-k的体积转移过来
            }
        }
    }
    for(int i = m; i >= v[u]; i--)//如果体积允许，将节点u加上
        f[u][i] = f[u][i - v[u]] + w[u];
    for(int i = 0; i < v[u]; i++)//如果体积不允许，那么节点u及其子树的所有物品都不能选，因此价值为0
        f[u][i] = 0;
}

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    int root = 0;
    for(int i = 1; i <= n; i++)
    {
        int p;
        cin >> v[i] >> w[i] >> p;
        if(p == -1) root = i;
        else add(p, i);
    }
    dfs(root);
    cout << f[root][m] << endl;
    return 0;
}