/**
使用面向对象,将数据进行封装
学习yxz的分析思路,进行模拟
喜欢模拟的朋友可以点进来看看
*/
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
public class Main{
public static int c; // 背包容量
public static void main(String[] argv){
Scanner in = new Scanner(System.in);
int N = in.nextInt();
c = in.nextInt();
// 将物品信息先存放到孤立“节点”中
TreeNode[] n = new TreeNode[N];
for(int i=0;i<N;i++)
n[i] = new TreeNode(in.nextInt(),in.nextInt(),in.nextInt());
in.close();
// 将树节点连接成一棵树
TreeNode root = null;
for(int i=0;i<N;i++){
if(n[i].p == -1) {
root = n[i];
continue;
}
n[n[i].p-1].childs.add(n[i]);
}
dfs(root);
System.out.println(root.rec[c]);
}
public static void dfs(TreeNode r){
for(TreeNode n : r.childs){
dfs(n);
for(int j=c-r.v;j>=0;j--){
for(int k=0;k<=j;k++){
r.rec[j] = Math.max(r.rec[j],r.rec[j-k] + n.rec[k]);
}
}
}
for(int i=c;i>=r.v;i--) r.rec[i] = r.rec[i-r.v]+r.w;
for(int i=0;i<r.v;i++) r.rec[i] = 0;
}
}
/**
对物品进信息行封装:
常规属性:vi wi pi
树节点属性: 存放子节点的链表
dp属性:int[] rec
参考yxz的dfs函数,以及状态含义 f[i][j] 为“以选择节点 i 为根的子树,所用背包容量为j时的最大价值”
可以在每一个节点中 定义一个长度=110 的一维数组 rec来记录:以该节点为根的树,尝试装入的最大价值物品的依赖背包问题
最终答案 存放在 root.rec[c] 处 c为背包容量
*/
class TreeNode{
int v;
int w;
int p;
int[] rec;
List[HTML_REMOVED] childs;
public TreeNode(int v,int w,int p){
this.v = v;
this.w = w;
this.p = p;
childs = new ArrayList<>();
rec = new int[110];
}
}