传送门：

思路：很明显忍者之间的关系是一个树形结构

先自底向上枚举管理者x，那么根据题意，我们就要从x的子树中选择尽量多的忍者，且工资总和不超过m

用一个可并堆

到一个点x，就把它的儿子节点的可并堆并起来

显然优先选工资低的，那么维护大根堆，不停地删堆顶，直到工资满足预算即可

#include
    
     #include
     
      #include
      
       #include
       
        typedef long long ll;const int maxn=100010,maxm=100010;using namespace std;int C[maxn],L[maxn],siz[maxn],root[maxn],n,m,pre[maxm],now[maxn],son[maxm],tot;ll ans,sum[maxn];void read(int &x){	char ch;	for (ch=getchar();!isdigit(ch);ch=getchar());	for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';}void add(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}struct Ltree{	int v[maxn],l[maxn],r[maxn],dis[maxn],tot;	int newnode(int val){v[++tot]=val,l[tot]=r[tot]=dis[tot]=0;return tot;}	int merge(int x,int y){		if (!x||!y) return x+y;		if (v[x]
        
         dis[l[x]]) swap(r[x],l[x]);		dis[x]=dis[r[x]]+1;		return x;	}	void pop(int &x){x=merge(l[x],r[x]);}	int top(int x){return v[x];}}h;void dfs(int x){	root[x]=h.newnode(C[x]);	siz[x]=1,sum[x]=C[x];	for (int y=now[x];y;y=pre[y]){		dfs(son[y]);		sum[x]+=sum[son[y]];		siz[x]+=siz[son[y]];		root[x]=h.merge(root[x],root[son[y]]);	}	for (;sum[x]>m;) sum[x]-=h.top(root[x]),h.pop(root[x]),siz[x]--;	ans=max(ans,1ll*L[x]*siz[x]);}int main(){	read(n),read(m);	for (int i=1,x;i<=n;i++) read(x),read(C[i]),read(L[i]),add(x,i);	dfs(1),printf("%lld\n",ans);	return 0;}