题目链接：戳我

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

左偏树，作为一个十分优秀的可并堆，我们这道题利用的就是这个数据结构。

左偏树不会？戳我

这里有一张来自HolseLee dalao的图：

因为是从下往上合并嘛。。所以dfs整棵树的时候一定注意要先把dfs递归放下去，等把所有的子树都处理完之后，才可以开始处理自己呀！！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 100010

using 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呜呜呜 哪个大佬来教教我啊