学习材料：https://wenku.baidu.com/view/029c886d1eb91a37f1115ce5.html
例题1：bzoj 2809 [Apio2012]dispatching
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2809
枚举每个点作为管理者，那么就是子树里选一些 c 最小的，看看最多能选即可。
想到线段树合并，维护区间 c 的和、个数，然后线段树上二分。
可以用左偏树。维护大根堆，当堆里元素代价总和大于限制时，弹掉代价最大的一些元素。（注意是一些元素而不是一个）
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } ll Mx(ll a,ll b){return a>b?a:b;} const int N=1e5+5; int n,m,vl[N],l[N],hd[N],xnt,to[N<<1],nxt[N<<1]; int rt[N],s[N],ct[N],dis[N],ls[N],rs[N],dep[N]; ll ans; void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;} int mrg(int x,int y) { if(!x||!y)return x|y; if(vl[x]<vl[y])swap(x,y); rs[x]=mrg(rs[x],y); if(dis[rs[x]]>dis[ls[x]])swap(ls[x],rs[x]); dis[x]=dis[rs[x]]+1; return x;/// } int del(int x) { return mrg(ls[x],rs[x]); } void dfs(int cr,int fa) { rt[cr]=cr; s[cr]=vl[cr]; ct[cr]=1; for(int i=hd[cr],v;i;i=nxt[i]) if((v=to[i])!=fa) { dfs(v,cr); rt[cr]=mrg(rt[cr],rt[v]); s[cr]+=s[v]; ct[cr]+=ct[v]; while(s[cr]>m)//while!! not if { s[cr]-=vl[rt[cr]]; ct[cr]--; rt[cr]=del(rt[cr]); } } ans=Mx(ans,(ll)l[cr]*ct[cr]); } int main() { n=rdn(); m=rdn(); dis[0]=-1;// for(int i=1,d;i<=n;i++) { d=rdn();if(i>1)add(d,i); vl[i]=rdn(); l[i]=rdn(); } dfs(1,0); printf("%lld ",ans); return 0; }
例题2：洛谷 3377 模板左偏树
题目：https://www.luogu.org/problemnew/show/P3377
真是模板。
同时再用一个并查集维护每个点在哪个堆即可。有删点，不用改变并查集的结构，只需给每个并查集的根记录一下该点集对应的左偏树的根是谁即可。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } const int N=1e5+5; int n,m,fa[N],rt[N],dis[N],ls[N],rs[N];bool vis[N]; struct Node{ int x,y; bool operator< (const Node &b)const {return x==b.x?y<b.y:x<b.x;} }a[N]; int fnd(int a){return fa[a]==a?a:fa[a]=fnd(fa[a]);} int mrg(int x,int y) { if(!x||!y)return x|y; if(a[y]<a[x])swap(x,y); rs[x]=mrg(rs[x],y); if(dis[rs[x]]>dis[ls[x]])swap(ls[x],rs[x]); dis[x]=dis[rs[x]]+1; return x; } int del(int x) { return mrg(ls[x],rs[x]); } int main() { n=rdn(); m=rdn(); dis[0]=-1;// for(int i=1;i<=n;i++) { fa[i]=i; rt[i]=i; a[i].x=rdn(); a[i].y=i; } for(int i=1,op,x,y;i<=m;i++) { op=rdn(); if(op==1) { x=rdn();y=rdn(); if(vis[x]||vis[y])continue; x=fnd(x); y=fnd(y); if(x==y)continue; fa[y]=x; rt[x]=mrg(rt[x],rt[y]); } else { x=rdn(); if(vis[x]){puts("-1");continue;} x=fnd(x); printf("%d ",a[rt[x]].x); vis[rt[x]]=1; rt[x]=del(rt[x]); } } return 0; }