update on 2024.9.18： 修正模板题题号，增加P2713

定义 $dep_x=\min(dep_{ls},dep_{rs})+1$

叶子节点的 $dep$ 为 $0$

考虑每次让 $dep_x+dep_y(\leq log_2n+log_2m)$ 减去1

单次复杂度 $O(log |x|+log|y|)$

时空复杂度 $O(mlogn)$

一些玄学：

不写 $dep$，在合并时用 $rand()$ 决定合并左儿子还是右儿子。（据说常数较大？）

(好用的！强推）

模板P3377

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long 
using namespace std;
const int MAXN = 1e5 + 10;
int n,m;
int a[MAXN],del[MAXN],fa[MAXN],ls[MAXN],rs[MAXN];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int merge(int x,int y){
	//printf("%d %d\n",x,y);
	if(!x||!y) return x+y;
	if(a[x]>a[y]) swap(x,y);
	if(rand()%2) ls[x]=merge(ls[x],y);
	else rs[x]=merge(rs[x],y);
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	FL(i,1,n) scanf("%d",&a[i]),fa[i]=i;
	FL(i,1,m){
		int op,x,y;
        scanf("%d%d",&op,&x);
        if(op==1){
            scanf("%d",&y);
            //printf("%d %d\n",x,y);
            if(del[x]||del[y]||find(x)==find(y)) continue;
            x=find(x);
			y=find(y);
			fa[x]=fa[y]=merge(x,y);
			//printf("%d %d\n",fa[x],fa[y]);
        }
        if(op==2){
            if(del[x]){
				puts("-1");
				continue;
			}
            x=find(x);
            printf("%d\n",a[x]);
        	del[x]=1;
        	fa[ls[x]]=fa[rs[x]]=fa[x]=merge(ls[x],rs[x]);
        	ls[x]=rs[x]=0;
        }
    }	
}

P1552 [APIO2012] 派遣

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define int long long 
using namespace std;
const int MAXN = 1e5 + 10;
int m,n;
int c[MAXN],a[MAXN],rt[MAXN],siz[MAXN],ans;
struct node{
    int v,nxt;
}e[MAXN<<1];
int head[MAXN],cnt=0;
void add(int u,int v){
	e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
struct tree{
    int ls,rs,d,val,sum,siz;
}z[MAXN];
void pushup(int x){
    z[x].sum=z[z[x].ls].sum+z[z[x].rs].sum+z[x].val;
    z[x].siz=z[z[x].ls].siz+z[z[x].rs].siz+1;
}
int merge(int x,int y){
    if(!x||!y) return x+y;
    if(z[x].val<z[y].val) swap(x,y);
    if(rand()&1) z[x].ls=merge(z[x].ls,y);
    else z[x].rs=merge(z[x].rs,y);
    pushup(x);
    return x;
}
void dfs(int x,int f){
    z[x].val=c[x];
    z[x].ls=z[x].rs=0;
	z[x].siz=1;
    z[x].sum=c[x];
    rt[x]=x;
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==f) continue;
        dfs(v,x);
        rt[x]=merge(rt[x],rt[v]);
    }
    while(z[rt[x]].sum>m&&z[rt[x]].siz) rt[x]=merge(z[rt[x]].ls,z[rt[x]].rs);
    ans=max(ans,z[rt[x]].siz*a[x]);
}
signed main(){
    scanf("%lld%lld",&n,&m);
    FL(i,1,n){
    	int x;
        scanf("%lld%lld%lld",&x,&c[i],&a[i]);
        add(x,i);
		add(i,x);
    }
    dfs(1,0);
    printf("%lld\n",ans);
    return 0;
}

P2713 罗马游戏

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 1e6 + 10;
int fa[MAXN],ls[MAXN],rs[MAXN],a[MAXN];
bool mk[MAXN];
int find(int x){
//	printf("x=%d\n",x);
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int merge(int x,int y){
	if(!x||!y) return x+y;
	if(a[x]>a[y]) swap(x,y);
	if(rand()&1) ls[x]=merge(ls[x],y);
	else rs[x]=merge(rs[x],y);
	return x;
}
int main(){
	int n,m;
	scanf("%d",&n);
	FL(i,1,n) scanf("%d",&a[i]),fa[i]=i;
	scanf("%d",&m);
	while(m--){
		char op;
		int x,y;
		scanf(" %c%d",&op,&x);
		if(op=='M'){
			scanf("%d",&y);
			int fx=find(x),fy=find(y);
			if(mk[x]||mk[y]||fx==fy) continue;
			fa[fx]=fa[fy]=merge(fx,fy);
		}
		else{
			if(mk[x]){
				puts("0");
				continue;
			}
			x=find(x);
			printf("%d\n",a[x]);
			mk[x]=1;
			fa[ls[x]]=fa[rs[x]]=fa[x]=merge(ls[x],rs[x]);
			ls[x]=rs[x]=0;
		}
	}
}