题目链接：戳我

就是尽可能地选取排名小的，加起来就可以了。然后我们考虑利用一个大根堆，一个一个合并，如果超过派遣的钱，我们就把费用最大的那个忍者丢出队列。

左偏树，作为一个十分优秀的可并堆，我们这道题利用的就是这个数据结构。
左偏树不会？戳我
这里有一张来自HolseLee dalao的图：

代码如下：

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define MAXN 100010using namespace std;int n,m,root,tt;int v[MAXN],rt[MAXN],siz[MAXN],head[MAXN];long long ans,sum[MAXN];struct Node{int ls,rs,dis,fa;long long val;}t[MAXN];struct Edge{int nxt,to;}edge[MAXN<<1];inline void add(int from,int to){edge[++tt].nxt=head[from],edge[tt].to=to,head[from]=tt;}inline int merge(int x,int y){ if(t[x].val==-1) x=0; if(t[y].val==-1) y=0; if(x==0||y==0) return x+y; if(t[x].val<t[y].val) swap(x,y); t[x].rs=merge(t[x].rs,y); t[t[x].rs].fa=x; if(t[t[x].ls].dis<t[t[x].rs].dis) swap(t[x].ls,t[x].rs); t[x].dis=t[t[x].rs].dis+1; return x;}inline int pop(int x){ t[t[x].ls].fa=t[t[x].rs].fa=0; t[x].val=-1; return merge(t[x].ls,t[x].rs);}inline void dfs(int x){ sum[x]=t[x].val,siz[x]=1; for(int i=head[x];i;i=edge[i].nxt) { dfs(edge[i].to); sum[x]+=sum[edge[i].to]; siz[x]+=siz[edge[i].to]; } for(int i=head[x];i;i=edge[i].nxt) rt[x]=merge(rt[x],rt[edge[i].to]); while(sum[x]>m&&siz[x]) { siz[x]--; sum[x]-=t[rt[x]].val; rt[x]=pop(rt[x]); } ans=max(ans,(long long)siz[x]*v[x]);}int main(){ #ifndef ONLINE_JUDGE freopen("ce.in","r",stdin); #endif scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int ff; scanf("%d%lld%d",&ff,&t[i].val,&v[i]); add(ff,i); if(ff==0) root=i; rt[i]=i; } dfs(root); printf("%lld\n",ans); return 0;}

本来想写一个pb_ds版本的，但是好像玩不转啊qwq呜呜呜 哪个大佬来教教我啊