01背包问题+树形DP

对于u这个节点，如果以方案来划分子节点，就退化成了爆搜
但是以体积来枚举子节点，因为体积不大，所以是一个很经典的优化
然后等于对子节点做对于体积的01背包

状态定义 $f[i][j]$ :考虑到节点 $i$ 且总使用体积为 $j$ 的最大价值

状态转移：枚举所有分配给子树的体积 $[m-v[i],0]\(倒序)$

$f[u][j]=max(f[u][j],f[u][j-k]+f[next][k])$

最后分类该节点本身：

物品选上$i$: $f[u][i]=f[u][i-v[u]]+w[u]$,$i\in{[m,v[u]]}$

不选上 $i$ :$f[u][i]=0$,$i\in{[0,v[u])}$

对于枚举方案数的情况，可以使用状态压缩来枚举所有信息。
参考金明的预算方案

枚举体积的时间复杂度 $O(N\*V\*V)$

枚举方案的时间复杂度 $O(N * M * 2^k)$

体积小枚举体积，如果子树的分枝都很小，那么就可以枚举方案。
如果权在边上，参考二叉苹果树

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=110*110;

int n,m;
int h[N],e[N],en[N],idx;
int v[N],w[N];
int f[N][N];

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

void dfs(int u)
{
    for(int i=h[u];i!=-1;i=en[i]){
        int next=e[i];
        dfs(next);
        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[next][k]);
    }
    for(int i=m;i>=v[u];i--) f[u][i]=f[u][i-v[u]]+w[u];
    for(int i=0;i<v[u];i++) f[u][i]=0;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int root;
    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;
}