APIO 2012 派遣（可并堆）

#include <cstdio>
using namespace std;

typedef long long LL;
const LL maxn=2e5+5;
void swap(LL &x,LL &y){ LL t=x; x=y; y=t; }
LL max(LL x,LL y){ return x<y?y:x; }

struct Edge{
    LL to,nxt;
}e[maxn];
LL cnte,fir[maxn],ans;
void addedge(LL x,LL y){
    Edge &ed=e[++cnte];
    ed.to=y; ed.nxt=fir[x]; fir[x]=cnte; }

LL n,M,rt,b[maxn],v[maxn],sum[maxn],cnt[maxn];
//要维护关于薪水b的大根堆 sum表示堆内所有b的和 cnt表示堆内有多少点

struct LHeap{
    LL l,r,dis,fa;
}h[maxn];

LL find(LL x){ return h[x].fa==x?x:find(h[x].fa); }

LL merge(LL x,LL y){  //把x和y为根的树合并
    if (!x||!y) return x+y;
    if (b[x]<b[y]) swap(x,y);
    LL &lx=h[x].l,&rx=h[x].r;
    rx=merge(rx,y); h[rx].fa=x;  //把右子树和y树合并
    if (h[lx].dis<h[rx].dis) swap(lx,rx);
    h[x].dis=h[rx].dis+1;
    sum[x]=sum[lx]+sum[rx]+b[x];
    cnt[x]=cnt[lx]+cnt[rx]+1;
    return x;  //返回根的编号
}

LL del(LL x){  //删除树x的根结点，返回新根的编号
    LL lx=h[x].l,rx=h[x].r;
    h[lx].fa=lx; h[rx].fa=rx;
    return merge(lx,rx);
}

LL dfs(LL x){  //返回合并后大根堆的根结点编号 刚开始的时候，x的堆根结点的编号就是x
    LL u=x;
    for (LL i=fir[x]; i; i=e[i].nxt)
        x=merge(dfs(e[i].to),x);  //不停合并子树的堆
    while (sum[x]>M) x=del(x);  //使得当前的堆的sumb<=M
    ans=max(ans,v[u]*cnt[x]);
    return x;
}

int main(){
    scanf("%lld%lld",&n,&M); LL t;
    for (LL i=1; i<=n; ++i){
        scanf("%lld%lld%lld",&t,&b[i],&v[i]);
        if (t) addedge(t,i); else rt=i;
        h[i].fa=i; sum[i]=b[i]; cnt[i]=1;
    }
    dfs(rt); printf("%lldn",ans);
    return 0;
}