1 # include<iostream>
2 # include<cstring>
3 # include<algorithm>
4 using namespace std;
5 const int N = 110;
6
7 int e[N], ne[N], idx;
8 int h[N];
9 int v[N], val[N];
10 int n, m;
11 int f[N][N];
12
13 void add(int a, int b) {
14 e[idx] = b;
15 ne[idx] = h[a];
16 h[a] = idx++;
17 }
18 void dfs(int u) {
19 for (int i = h[u]; ~i; i = ne[i]) /*循环子节点*/
20 {
21 int son = e[i];
22 dfs(e[i]);/*递归子节点*/
23
24 for (int j = m - v[u]; j >= 0; --j)/*循环体积*/
25 for (int k = 0; k <= j; ++k)/*循环决策*/
26 f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
27 }
28 for (int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + val[u];
29 for (int i = 0; i < v[u]; ++i) f[u][i] = 0;
30 }
31
32 int main() {
33 cin >> n >> m;
34 int root;/*根节点*/
35 memset(h,-1,sizeof h);/*初始化头结点*/
36 for (int i = 1; i <= n; ++i) {
37 int c;
38 cin >> v[i] >> val[i] >> c;
39 if (c == -1) root = i;
40 else add(c, i);
41 }
42
43 dfs(root);
44
45 cout << f[root][m] << endl;
46 return 0;
47 }
f[u][j]表示在根节点为u，体积为j的情况下的最大价值
树形结构的dp问题，重点在于理解在树形结构的决策选择
因为题目限制只要选择子节点，那么头结点必须选择，所以在循环体积的时候，因为是对于子节点进行循环体积
所以要求要在体积上为父节点的体积预留位置，所以才有：
for (int j = m - v[u](这一步就是在为父节点预留体积); j >= 0; --j)
而在后续的的过程中，因为在递归字节的时候为父节点预留了体积，所以在结束对子节点的递归后
需要把之前预留的位置将父节点的信息加进去，也就是：
for (int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + val[u];
对于之前预留的体积将父节点的信息加入进去，
for (int i = 0; i < v[u]; ++i) f[u][i] = 0;
因为只要选择子节点就需要选择父节点，所以对于小于父节点的部分在决策中是绝对选择不到的
这就需要将其价值清0
