#有依赖的背包问题 ——AcWing 10. 有依赖的背包问题

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N], v[N], w[N], n, m, root ;
//f[x][v] 即 以x为根的子树 在容量不超过v时 的最大价值
vector<int> g[N];
int dfs(int x){
    for(int i = v[x]; i <= m; i ++) 
        f[x][i] = w[x];
  	  //点x必须选，所以初始化f[x][v[x] ~ m]= w[x]
    for(int i = 0; i < g[x].size(); i ++){
        int y = g[x][i];
        dfs(y);
        //找子树；
        for(int j = m; j >= v[x]; j --)
        //由最底的 叶 开始 更新f[x][j]  一直到 根 ;
        //j的范围为v[x] ~ m, 小于v[x]无法选择以x为子树的物品
            for(int k = 0; k <= j - v[x]; k ++)
                 //k是 分给 子树y 的空间；
          	 	 //k不能大于j-v[x],不然无法选根物品x
                f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);
	                //f[y][k]为子树在不超过k的情况下最大价值；
	                //这里把 f[x][0 ~ j] 看做一个 物品组；
	                //每一个 f[x][j] 是一个物品；
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n;i ++){
        int fa; 
        cin >> v[i] >> w[i] >> fa;
        if(fa == -1)
            root = i;
        else
            g[fa].push_back(i);
    }
    dfs(root);
    cout << f[root][m];
    return 0;
}

撒花。