【BZOJ】2809: [Apio2012]dispatching（左偏树）

题目

传送门：QWQ

分析

显然是一个资瓷合并的堆

现学了一发左偏树：教程

然后就没了

代码

#include <bits/stdc++.h>
#define lc son[x][0]
#define rc son[x][1]
using namespace std;
typedef long long ll; ll ans=-1e7;
const int maxn=100500;
ll v[maxn], siz[maxn], sum[maxn]; int  rt[maxn], son[maxn][2], cnt;
ll val[maxn], l[maxn], n, m;
vector<int> G[maxn];
int merge(int x,int y){
    if(x==0||y==0) return x+y; 
    if(v[x]<v[y]) swap(x,y);
    rc=merge(rc,y);    swap(lc,rc);
    return x;
}
void pop(int& x){ x=merge(lc,rc); }
int top(int x){ return v[x]; }
void dfs(int x){
    rt[x]=++cnt; v[cnt]=val[x];
    siz[x]=1; sum[x]=val[x];
    for(int i=0;i<G[x].size();i++){
        int v=G[x][i]; dfs(v);
        siz[x]+=siz[v]; sum[x]+=sum[v];
        rt[x]=merge(rt[x],rt[v]);
    }
    for(;sum[x]>m;){
        sum[x]-=top(rt[x]);
        pop(rt[x]); siz[x]--;
    }
    ans=max(ans,(l[x]*siz[x]));
}
int main(){
    int a, root=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%lld%lld",&a,&val[i],&l[i]);
        G[a].push_back(i); if(a==0) root=i;
    }
    dfs(root);
    printf("%lld
",ans);
    return 0;
}