可能大家都知道树上背包合并对子树大小取可以优化到。但是对于树上依赖背包问题，背包合并的复杂度仍不能接受。考虑形式化的问题：

一棵个结点有根树，每个结点有个价格为，价值为的物品。除了根结点，要购买某个结点的物品必须在它的父节点购买至少一件。求总费用为时的最大化价值。。

一个朴素的 DP 是表示在结点的子树中购买费用不超过的物品的最大价值。转移时进行背包合并，总复杂度。

我们考虑换一种 DP 的顺序。朴素 DP 是以递归子结构的形式进行 DP。考虑按照 DFS 序 DP。

我们以后序遍历（先按序遍历子节点，再遍历根结点）的方式求出结点的 DFS 序。则对于结点，设其 DFS 序为，记它的子树大小为。同时我们记 DFS 序为的结点为。

通俗地说，我们设表示在 DFS 序小于等于的结点构成的连通块中选物品，总费用不超过时的最大价值。转移的时候枚举上选不选物品，从转移。

如果上述状态定义不能理解，我们接下来做一些严谨的描述。首先给出后序遍历 DFS 序的一些性质：

  1. 如果不是叶子结点，则是的儿子（儿子序列中的最后一个儿子）
  2. 对于树中的任意结点，如果，则是离最近的，存在前兄弟结点的祖先结点（也可能是自己）的前兄弟结点。说的很绕口，可以自己画图理解一下。

知道这个以后，我们定义，即 DFS 序为的结点由性质 2 导出的结点；如果则令。

因此更严谨地说，我们设表示在子树构成的森林中按依赖关系选物品，总费用不超过的最大价值。

转移的时候，如果上选物品才能从转移（要选子节点必须选父节点上的东西）。此外在任何时候都可以从转移。

对于上述多重依赖背包问题，我们首先可以从转移到（直接复制）。然后我们强制选一个物品，可以从转移过来。然后对于剩下的个物品，使用单调队列优化多重背包或者二进制分组来更新即可。复杂度或。

//ZR 309
#include<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}/*}}}*/
/******************heading******************/
const int N=5000,M=5000;

struct qxx{int nex,t;};
qxx e[N*2];
int h[N],le;
void add_path(int f,int t){e[++le]=(qxx){h[f],t},h[f]=le;}
#define FORe(i,u,v) for(int i=h[u],v;v=e[i].t,i;i=e[i].nex)

int n,m;
int w[N],s[N],c[N];

int totdfn,sz[N];
int f[N][M];
int dfs(int u){
    sz[u]=1;
    FORe(i,u,v)sz[u]+=dfs(v);
    int i=++totdfn;
    int lim=s[u];
    f[i][0]=0;
    // f[i,j] <- f[i-sz[u],j] , f[i-1,j]
    for(int j=m;j>=0;j--){
        if(j>=c[u]) f[i][j]=max(f[i][j],f[i-1][j-c[u]]+w[u]);// 至少选一个物品，才能从 i-1 转移
        f[i][j]=max(f[i][j],f[i-sz[u]][j]);
    }
    --lim;
    for(int k=1;k<=lim;lim-=k,k<<=1){// 在之前 i-1 和 i-sz 转移的基础上，加入多个物品（二进制）
        for(int j=m;j>=k*c[u];j--){
            f[i][j]=max(f[i][j],f[i][j-k*c[u]]+k*w[u]);
        }
    }
    if(lim){// 剩下一个二进制余项
        for(int j=m;j>=lim*c[u];j--){
            f[i][j]=max(f[i][j],f[i][j-lim*c[u]]+lim*w[u]);
        }
    }
    return sz[u];
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,2,n){
        int x;
        scanf("%d",&x);
        add_path(x,i);
    }
    FOR(i,1,n){
        scanf("%d%d%d",&w[i],&c[i],&s[i]);
    }
    dfs(1);
    FOR(i,1,m)printf("%d%c",f[totdfn][i]," \n"[i==m]);
    return 0;
}