传送门

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 110;
vector<int> e[N];
int v[N], w[N];
int n, m;

int f[N][N]; //f(i, j)表示以i为根节点的块中，体积不超过j的最大价值
// 集合是由儿子转移过来
// 先遍历儿子，满足无后效性
// f(i, j) = max(f(i, j - v(self)) + w[i], f(i, j - v(k)) + f[son][v]);
// v(self)为自身的体积, v(k)为枚举的体积
// 因为i作为根节点必须选择，首先需要预处理

void dfs(int u)
{
    //肯定从上一层更新到下一层，因为该节点是必选的，所以需要先预处理
    for (int i = m; i >= v[u]; i --) f[u][i] = f[u][i - v[u]] + w[u];

    for (int i = 0; i < e[u].size(); i ++)
    {
        int son = e[u][i]; //拿到该节点

        dfs(son); // dfs先更新子节点，才有权更新本节点

        //枚举合法体积，从大到小枚举，如果从小到大实际上是由本层转移而来，显然不满足，破坏了后效性
        for (int j = m; j >= v[u]; j --) 
        {
            for (int k = 0; k <= j - v[u]; k ++)
            {
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]); 
            }
        }

    }

}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m;

    int root = -1;

    for (int i = 1; i <= n; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;

        v[i] = a, w[i] = b;

        if (c == -1) root = i;
        else e[c].push_back(i);
    }

    dfs(root);

    cout << f[root][m] << "\n";

    return 0;
}