//用类似有依赖的背包的写法过不了,数据量太大,只能优化 //特别要注意这里是找dp[0][i]中的最大值 #include<iostream> #include<stdio.h> #include<string.h> #define maxn 100005 using namespace std; int n,g,idx,ans; int c[maxn],v[maxn],head[maxn],use[maxn]; int dp[505][10005]; struct node { int to; int next; }edg[maxn]; inline int max(int x,int y) //用inline来省时 { if(x>y) return x; return y; } void init(int n) { memset(dp[0],0,sizeof(int)*(g+1)); memset(head,-1,sizeof(int)*(n+1)); memset(use,0,sizeof(int)*(n+1)); idx=0; ans=0; } void addNode(int from,int to) { edg[idx].to=to; edg[idx].next=head[from]; head[from]=idx++; } void dfs(int now,int lim)//表示已选x的情况下,用lim更新子节点 { for(int i=head[now];i!=-1;i=edg[i].next) { int j=edg[i].to; //不是叶子节点 if(use[j]) { if(lim-c[j]>=0) { for(int k=lim-c[j];k>=0;k--) //给子树初值 dp[j][k]=dp[now][k]; dfs(j,lim-c[j]); //让子树打包 for(int k=c[j];k<=lim;k++) //合并 { dp[now][k]=max(dp[now][k],dp[j][k-c[j]]+v[j]);//选或不选子树的某个背包 } } } else { for(int k=lim;k>=c[j];k--) { dp[now][k]=max(dp[now][k-c[j]]+v[j],dp[now][k]);//01背包 } } } } int main() { int i; v[0]=c[0]=0; while(scanf("%d %d",&n,&g)!=EOF) { init(n); for( i=1;i<=n;i++) { int f; scanf("%d %d %d",&c[i],&v[i],&f); if(i==f) f=0; use[f]++; addNode(f,i); } dfs(0,g); for( i=0;i<=g;i++) ans=max(ans,dp[0][i]); printf("%d\n",ans); } return 0; }