rt，这里暴力两次修改，有没有大佬帮忙优化空间QAQ。

#include<cstdio>
#include<iostream>
#include<utility>
#define pb push_back
#define is insert
#define fi first
#define se second
#define bg begin
#define INF INT_MAX
#define Mod(a,m) (((a)%(m)+(m))%(m))
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
const int N=1e5+5;
const int V=8.3e6+5;
int n,m,t,tot;
struct PersistentSegmentTree{
	int tot,rt[N];
	struct Node{
		int lc,rc;
		pii val;
	}tr[V];
	void build(int u,int l,int r){
		if(l==r){tr[u].val={l,1};return;}
		int mid=l+r>>1;
		build(tr[u].lc=++tot,l,mid);
		build(tr[u].rc=++tot,mid+1,r);
	}
	void change(int u,int lstu,int l,int r,int pos,pii k){
		tr[u]=tr[lstu];
		if(l==r){tr[u].val=k;return;}
		int mid=l+r>>1;
		if(pos<=mid) change(tr[u].lc=++tot,tr[lstu].lc,l,mid,pos,k);
		else change(tr[u].rc=++tot,tr[lstu].rc,mid+1,r,pos,k);
	}
	void add(int u,int lstu,int l,int r,int pos,int k){
		tr[u]=tr[lstu];
		if(l==r){tr[u].val.second+=k;return;}
		int mid=l+r>>1;
		if(pos<=mid) add(tr[u].lc=++tot,tr[lstu].lc,l,mid,pos,k);
		else add(tr[u].rc=++tot,tr[lstu].rc,mid+1,r,pos,k);
	}
	pii query(int u,int l,int r,int pos){
		if(l==r) return tr[u].val;
		int mid=l+r>>1;
		if(pos<=mid) return query(tr[u].lc,l,mid,pos);
		else return query(tr[u].rc,mid+1,r,pos);
	}
}T;
int find(int x){
	if(x==T.query(T.rt[t<<1],1,n,x).fi) return x;
	else return find(T.query(T.rt[t<<1],1,n,x).fi);
}
void merge(int x,int y){
	x=find(x),y=find(y);
	if(x!=y){
		if(T.query(T.rt[(t<<1)-2],1,n,x).se>T.query(T.rt[(t<<1)-2],1,n,y).se) std::swap(x,y);
		T.change(T.rt[(t<<1)-1]=++T.tot,T.rt[(t<<1)-2],1,n,x,{y,0});
		T.add(T.rt[t<<1]=++T.tot,T.rt[(t<<1)-1],1,n,y,T.query(T.rt[(t<<1)-2],1,n,x).se);
	}
}
bool check(int x,int y){return (find(x)==find(y));}
int main(){
	scanf("%d%d",&n,&m);
	T.build(T.rt[0]=++T.tot,1,n);
	short op,a,b,k;
	for(t=1;t<=m;t++){
		scanf("%d",&op);
		if(op==1) scanf("%d%d",&a,&b),T.rt[t<<1]=T.rt[(t<<1)-2],merge(a,b);
		if(op==2) scanf("%d",&k),T.rt[t<<1]=T.rt[k<<1];
		if(op==3) scanf("%d%d",&a,&b),T.rt[t<<1]=T.rt[(t<<1)-2],printf("%d\n",check(a,b));
	}
	return 0;
}