BZOJ 2809: [Apio2012]dispatching [斜堆]

题意：主席树做法见上一题

---

我曾发过誓再也不写左偏树(期末考试前一天下午5个小时没写出棘手的操作)

于是我来写斜堆啦

从叶子往根合并，维护斜堆就行了

题目连拓扑序都给你了...

说一下斜堆的操作：

合并：无脑交换一次左右子树

删除：合并左右子树代替自己

然后每个点保存一个根

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define lc t[x].l

#define rc t[x].r

typedef long long ll;

const int N=1e5+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,m;

struct Ninjia{

    int w,li;

}a[N];

struct Edge{

    int v,ne;

}e[N];

int h[N],cnt;

inline void ins(int u,int v){

    cnt++;

    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;

}

struct Node{

    int l,r,size,v;

    ll sum;

}t[N];

int rt[N];

inline void pushUp(int x){

    t[x].sum=t[lc].sum+t[rc].sum+t[x].v;

    t[x].size=t[lc].size+t[rc].size+;

}

int Merge(int x,int y){

    if(!x||!y) return x|y;

    if(t[x].v<t[y].v) swap(x,y);

    rc=Merge(rc,y);

    pushUp(x);

    swap(lc,rc);

    return x;

}

inline void Del(int &x){x=Merge(lc,rc);}

int main(){

    freopen("in","r",stdin);

    n=read();m=read();

    for(int i=;i<=n;i++){

        int u=read();ins(u,i);

        a[i].w=read(),a[i].li=read(),rt[i]=i;

        t[i].size=;t[i].v=t[i].sum=a[i].w;

    }

    ll ans=;

    for(int u=n;u>=;u--){//printf("u %d\n",u);

        for(int i=h[u];i;i=e[i].ne) rt[u]=Merge(rt[u],rt[e[i].v]);

        while(t[rt[u]].sum>m) Del(rt[u]);

        //printf("t %d %lld %d \n",a[u].li,t[rt[u]].sum,t[rt[u]].size);

        ans=max(ans,(ll)a[u].li*t[rt[u]].size);

    }

    printf("%lld",ans);

}