$Chat$
哈哈哈我xj用dfs序乱搞竟然炸出了66分....（其实还是数据水，逃）
$Sol$
首先我们应该知道，一个人他自己的满意度与他子树所有节点的领导力是无关的，一个人的满意度受它子树影响只通过选子树的数量来体现。
因为薪水预算是有限的，而我们又想获得更多的子树，那么我们肯定想要子树薪水排名前$k$个的（满足不超过总预算）。我的暴力想法是每次排序来维护的，其实这里正解是用左偏树来维护的。（嘤我只写过左偏树板子而且不太理解）。
我们每次都尽量把一个节点的所有子树都选上，然后每次用可并堆找出花费最大的点干掉（即维护大根堆），直到满足条件。为什么要用可并堆呢？在这个树形结构中，根（最大的）被干掉后，我们要把它的左儿子和右儿子合并。这个时候用左偏树再合适不过了。
上述算法的实现用到了树形dp（递归）的思想。
$Code$
因为没写过非板子的左偏树题目...所以这里写清楚些。$fa[]$记录的是这个点的根。开始时这个节点的根等于它自己。$merge$函数返回的也是根。
#include<cstdio>
#include<algorithm>
#define maxn 100090 using namespace std;
typedef long long ll; int n,m,tot;
int head[maxn],fa[maxn],dis[maxn],lch[maxn],rch[maxn],size[maxn];
ll ans,v[maxn],val[maxn],sum[maxn];
int T[maxn][];
struct node{
int to,next;
}edge[maxn*]; void add(int x,int y)
{
edge[++tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
} int merge(int x,int y)
{
if(x==||y==) return x+y;
if(v[x]<v[y]||(v[x]==v[y]&&x>y)) swap(x,y);
rch[x]=merge(rch[x],y);
fa[rch[x]]=y;
if(dis[lch[x]]<dis[rch[x]]) swap(lch[x],rch[x]);
dis[x]=dis[rch[x]]+;
return x;
} void dfs(int u,int f)
{
fa[u]=u;size[u]=;sum[u]=v[u];
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==f) continue;
dfs(v,u);
size[u]+=size[v];sum[u]+=sum[v];
fa[u]=merge(fa[u],fa[v]);
}
while(sum[u]>m&&size[u])
{
sum[u]-=v[fa[u]];
size[u]--;
fa[u]=merge(lch[fa[u]],rch[fa[u]]);
}
ans=max(ans,1ll*size[u]*val[u]);
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
int x=;scanf("%d",&x);
add(i,x);add(x,i);
scanf("%lld%lld",&v[i],&val[i]);
}
dfs(,);
printf("%lld",ans);
return ;
}