这下不得不求助了

#include<bits/stdc++.h>
using namespace std;
/*
用主席树维护fa数组 
*/
struct node{
	int dep;
	int faa;
	int ls;
	int rs;
	int le;
	int ri;
}tree[80000007];
int cnt=1;
int roots[400005]; 
void build(int rt,int L,int R){
	tree[rt].le=L;
	tree[rt].ri=R;
	int mid=(L+R)>>1;
	if(L==R){
		tree[rt].faa=L;
		tree[rt].dep=1;
		return; 
	}	
	tree[rt].ls=++cnt;
	tree[rt].rs=++cnt;
	build(tree[rt].ls,L,mid);
	build(tree[rt].rs,mid+1,R);
	
}
int newnode(int old){
	cnt++;
	int u=cnt;
	tree[u]=tree[old];
	tree[u].ls=tree[u].rs=0;
	return u;
}
pair<int,int> getpos(int proot,int pos){//返回深度和fa 
	int le=tree[proot].le;
	int ri=tree[proot].ri;
	if(pos<le||pos>ri){
		return make_pair(0,0);
	}
	if(le==ri){
		return make_pair(tree[proot].dep,tree[proot].faa);
	}
	pair<int,int> leans=getpos(tree[proot].ls,pos);
	pair<int,int> rians=getpos(tree[proot].rs,pos);
	pair<int,int> ret=make_pair(leans.first+rians.first,leans.second+rians.second);
	return ret;
}
int getfa(int rt,int x){
	pair<int,int>tox=getpos(rt,x);
	int fax=tox.second;
	if(fax==x){
		return x;
	}
	else return getfa(rt,tox.second);
}
int changefa(int newrt,int rt,int pos,int changeval){
	int le=tree[rt].le;
	int ri=tree[rt].ri;
	if(pos<le||pos>ri){
		if(newrt){
			return newrt;
		}
		return rt;
	}
	if(!newrt){
		newrt=newnode(rt); 
	}
	
	if(le==ri){
		tree[newrt].faa=changeval;
		return newrt;
	}
	tree[newrt].ls=changefa(tree[newrt].ls,tree[rt].ls,pos,changeval);
	tree[newrt].rs=changefa(tree[newrt].rs,tree[rt].rs,pos,changeval);
	return newrt;
}
int changedep(int newrt,int rt,int pos,int changeval){
	int le=tree[rt].le;
	int ri=tree[rt].ri;
	if(pos<le||pos>ri){
		if(newrt){
			return newrt;
		}
		return rt;
	}
	if(!newrt){
		newrt=newnode(rt); 
	}
	
	if(le==ri){
		tree[newrt].dep=changeval;
		return newrt;
	}
	tree[newrt].ls=changedep(tree[newrt].ls,tree[rt].ls,pos,changeval);
	tree[newrt].rs=changedep(tree[newrt].rs,tree[rt].rs,pos,changeval);
	return newrt;
}
int unite(int rt,int a,int b){
	pair<int,int> A=getpos(rt,a);
	pair<int,int> B=getpos(rt,b);

	int faA=A.second;
	int faB=B.second;
	faA=getfa(rt,faA);
	faB=getfa(rt,faB);
	pair<int,int>AA=getpos(rt,faA);
	pair<int,int>BB=getpos(rt,faB);	
	int depa=AA.first;
	int depb=BB.first;
	if(depa<depb){//让A的深度更大，把B连到A上。 
		swap(AA,BB);
		swap(depa,depb);
		swap(a,b);
	}
	//现在我需要修改B的fa和A的dep
	int u=0;
    u=changefa(u,rt,faB,AA.second);
    if(depa==depb){
    	u=changedep(u,rt,faA,AA.first+1);	
	}
    
    return u;

	 
}
bool judge(int rt,int a,int b){
    pair<int,int> A=getpos(rt,a);
	pair<int,int> B=getpos(rt,b);

	int faA=A.second;
	int faB=B.second;
	faA=getfa(rt,faA);
	faB=getfa(rt,faB);
    if(faA==faB){
        return 1;
    }
    else{
        return 0;
    }
}
int main(){
	ios::sync_with_stdio(false);
	roots[1]=1;
	int n,m;
	cin >> n >>m;
	int now=1;
	build(roots[1],1,n);
	while(m--){
		now++;
		int op;
		cin >>op;
		if(op==1){
			int a,b;
			cin >>a >>b;
			roots[now]=unite(roots[now-1],a,b);
		}
		else if(op==2){
			int k;
			cin >>k;
			roots[now]=roots[k+1];
		}
		else{
			int a,b;
			cin >>a >>b;
			roots[now]=roots[now-1];
			bool pron=judge(roots[now],a,b);
			cout<<pron<<endl; 
		}
	}
	
}