二刷提高课，题解目录在这里— 提高课的题解目录

有依赖背包问题，问题的核心是当我们选择了子节点，一定也要选取父节点
如果我们直接强行将其装换为线性关系(直接进行分组)，
我们会发现每一组都会有很多可能因为每个点都可能在某个组内共有2^100种
这显然不能用方案数来分类的，
而树的结构我们一般以每个子树来看，然后子树影响父节点最终得出我们需要的结果
但是如何划分子树呢？不能通过方案数划分，我们发现体积的数据量很小
所以我们可以尝试使用体积来划分，即f[i][j]表示以i为根体积不超过j的最大价值

第一种方法：通过得到所分类的体积子树的最大值从而回溯求出对应父节点的最大值（核心思想）

#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
int h[N],de[N],ne[N];
int dix,root,n,m;
int v[N],w[N],f[N][N];
int add(int a,int b)
{
    de[dix]=b,ne[dix]=h[a],h[a]=dix++;
}
int dfs(int u)
{
    //注意这里刚开始对子树枚举的是体积从0~m-v[u]所能构成的最大值
    //这里是放在下面，在没加上父节点的体积时，子节点总体积是不可能大于m-v[u]
    //否则当加上父节点的v[u]就会超出限制
    for(int i=h[u];~i;i=ne[i])
    {
        int son=de[i];
        dfs(son);
        for(int j=m-v[u];j>=0;j--)//枚举体积需要从大到小因为存了上个子节点的信息
        {
            for(int k=0;k<=j;k++)
            {
                f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
                //循环决策：意为选取这个儿子的多少体积能达到最大
            }
        }
    }
    for(int j=m;j>=v[u];j--)f[u][j]=f[u][j-v[u]]+w[u];//加上根节点的价值
    //在本子树中小于v[i]的是不存在的（因为根节点就有v[i]了所以只能不取这个子树的任何节点）
    for(int i=0;i<v[u];i++)f[u][i]=0;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    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];
    return 0;
}

第二种方法：父节点与子节点同时计算，不用先算出子节点所构成的可能体积(更简洁)

int dfs(int u)
{
    for(int i=v[u];i<=m;i++)f[u][i]=w[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int son=de[i];
        dfs(son);
        for(int j=m;j>=v[u];j--)
        {
            for(int k=0;k<=m-v[u];k++)
            {
                if(j+k<=m)f[u][j+k]=max(f[u][j+k],f[u][j]+f[son][k]);
            }
        }
    }
}