题意：主席树做法见上一题
我曾发过誓再也不写左偏树(期末考试前一天下午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+5,INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0'; 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+1; } 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=1;i<=n;i++){ int u=read();ins(u,i); a[i].w=read(),a[i].li=read(),rt[i]=i; t[i].size=1;t[i].v=t[i].sum=a[i].w; } ll ans=0; for(int u=n;u>=1;u--){//printf("u %d ",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 ",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); }