算法理解
ybt上讲的挺清楚的。。。
T1：
注：看洛谷原题，其中父节点编号是小于该节点的，我们把该节点向父节点上合并，为什么这样做？因为树的深度不定dfs会爆栈
需要维护每个节点在左偏树上对应的根
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define ls(x) pq[x].ls
#define rs(x) pq[x].rs
#define key(x) pq[x].key
#define dist(x) pq[x].dist
using namespace std;
const int N=1e5+5;
struct prique{int ls,rs,key,dist;void init(int x){ls=rs=dist=0;key=x;}
}pq[N];
int merge(int A,int B){if(!A) return B;if(!B) return A;if(key(A)<key(B)) swap(A,B);//大根堆rs(A)=merge(rs(A),B);if(!ls(A)||dist(ls(A))<dist(rs(A))) swap(ls(A),rs(A));if(rs(A)) dist(A)=dist(rs(A))+1;else dist(A)=0;return A;
}
int n,m;
int cnt[N],c[N],rt[N],l[N],fa[N];
ll sum[N];
ll ans;
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int u;scanf("%d%d%d",&fa[i],&c[i],&l[i]);pq[i].init(c[i]);rt[i]=i;cnt[i]=1;sum[i]=c[i];}for(int i=n;i>=1;i--){ans=max(ans,(ll)cnt[rt[i]]*l[i]);//统计答案要每个点都统计到，不能放在结尾，因为cnt值会变int x=rt[i],y=rt[fa[i]];int cn=cnt[y];ll su=sum[y];cn+=cnt[x],su+=sum[x];y=merge(x,y);while(su>m){cn--;su-=c[y];y=merge(ls(y),rs(y));}rt[fa[i]]=y;cnt[y]=cn;sum[y]=su;}printf("%lld\n",ans);
}