银牌题，zlt差点ak。
发现我们只关注保留下来的结点，每个保留的结点的父亲是他祖先中第一个保留的结点，则数颜色不同的条件相当于新树相邻结点颜色不同。
考虑dp，设 \(dp_{u,X,0/1}\) 表示 \(u\) 子树内最上方的结点颜色为 \(0/1\)，树的总重量为 \(X\) 的最大价值。每次转移就是暴力做 \((max,+)\) 卷积，或者说合并背包，复杂度是 \(X^2\) 的，总复杂度 \(nX^2\)，无法接受。
我们发现，合并背包的复杂度很大，但是由于 \(n\) 很小，一个一个加入甚至比合并快。这启示我们使用启发式合并。每次继承重儿子的两个背包，对于轻儿子，我们暴力扫一遍，加入之前做的背包，更新当前的背包状态。如果要求解所有子树，保留重儿子的答案，其他子树重新计算即可。
具体的，我们背包传一个大小为 \(X\) 的数组，表示之前做的背包，之后做的背包就以这个背包为基础，得到颜色 \(0/1\) 的两个背包，即为所需要的。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=205,inf=1e18;
int n,X,p[maxn],b[maxn],w[maxn],c[maxn],son[maxn],siz[maxn];
vector<int> G[maxn];
void predfs(int u)
{
siz[u]=1;
for(int v:G[u])
{
predfs(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
int ans[maxn];
vector<int> ini;
pair< vector<int>,vector<int> > dfs(int u,vector<int> dp,bool f)
{
if(f)for(int v:G[u])if(v!=son[u])dfs(v,dp,1);
vector<int> ndp[2];
if(!son[u])ndp[0]=ndp[1]=dp;
else
{
auto pp=dfs(son[u],dp,f);
ndp[0]=pp.first;
ndp[1]=pp.second;
for(int v:G[u])
if(v!=son[u])
{
ndp[0]=dfs(v,ndp[0],0).first;
ndp[1]=dfs(v,ndp[1],0).second;
}
}
for(int i=0;i<=X-w[u];i++)
{
ndp[c[u]][i+w[u]]=max(ndp[c[u]][i+w[u]],ndp[1-c[u]][i]+b[u]);
if(f)ans[u]=max(ans[u],ndp[1-c[u]][i]+b[u]);
}
return {ndp[0],ndp[1]};
}
signed main()
{
cin>>n>>X;for(int i=2;i<=n;i++)cin>>p[i],G[p[i]].push_back(i);
for(int i=1;i<=n;i++)cin>>b[i]>>w[i]>>c[i];
ini=vector<int>(X+1,-inf);ini[0]=0;
predfs(1);
dfs(1,ini,1);
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
return 0;
}