昨日做题时，见久不作过可持久化并查集矣，将忘光矣，乃有此博客。

可持久化并查集和普通并查集差不多，只是多了一个回退的操作。

一般支持的操作为：

  1. a b 合并a,b所在集合

  2. k 回到第k次操作之后的状态(查询算作操作)

  3. a b 询问a,b是否属于同一集合，是则输出1否则输出0

怎么实现回退操作呢？我们就把普通的 f[] 数组变为可持久化的数组即可。但是我们不能路径压缩（会破坏原本树的结构），所以我们还要维护树的高度，来按秩合并。

例题：可持久化并查集例题

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int rt1[N],rt2[N],n,m,cnt;
struct node{int l,r,s;}t[N*40];
void build(int l,int r,int &x){
	x=++cnt;
	if(l==r){t[x].s=l;	return ;}
	int mid=l+r>>1;
	build(l,mid,t[x].l); build(mid+1,r,t[x].r);
}
void change(int l,int r,int &x,int y,int pos,int val){
	x=++cnt; t[x]=t[y];
	if(l==r){t[x].s=val; return ;}
	int mid=l+r>>1;
	if(pos<=mid)	change(l,mid,t[x].l,t[y].l,pos,val);
	else	change(mid+1,r,t[x].r,t[y].r,pos,val);
}
int ask(int l,int r,int x,int pos){
	if(l==r)	return t[x].s;
	int mid=l+r>>1;
	if(pos<=mid)	return ask(l,mid,t[x].l,pos);
	else	return ask(mid+1,r,t[x].r,pos);
}
int find(int x,int k){
	int fa=ask(1,n,rt1[k],x);
	return x==fa?x:find(fa,k);
}
void merge(int x,int y,int k){
	x=find(x,k-1),y=find(y,k-1);
	if(x==y){rt1[k]=rt1[k-1],rt2[k]=rt2[k-1];	return ;}
	int hx=ask(1,n,rt2[k-1],x),hy=ask(1,n,rt2[k-1],y);
	if(hx>hy){change(1,n,rt1[k],rt1[k-1],y,x); rt2[k]=rt2[k-1];}
	else if(hy>hx){change(1,n,rt1[k],rt1[k-1],x,y); rt2[k]=rt2[k-1];}
	else if(hx==hy){
		change(1,n,rt1[k],rt1[k-1],x,y);
		change(1,n,rt2[k],rt2[k-1],y,hx+1);
	}
}
signed main(){
	cin>>n>>m; build(1,n,rt1[0]);
	for(int i=1,op,a,b;i<=m;i++){
		scanf("%d %d",&op,&a);
		if(op==1)	scanf("%d",&b),merge(a,b,i);
		else if(op==2)	rt1[i]=rt1[a],rt2[i]=rt2[a];
		else{
			rt1[i]=rt1[i-1],rt2[i]=rt2[i-1];
			scanf("%d",&b),printf("%d\n",find(a,i)==find(b,i));
		}
	}
	return 0;
}