代码

#include<bits/stdc++.h>

using namespace std;

const int N(1e5+5);

int n,m;
int cnt;
int root[N<<1];

struct tree{
	int l,r;
	int fa,dep;
}tr[N<<7];

inline void build(int &p,int l,int r){
	
	p=++cnt;
	
	if(l==r){
		tr[p].fa=l;
		return;
	}
	
	build(tr[p].l,l,l+r>>1);
	build(tr[p].r,(l+r>>1)+1,r);
	
	return;
}

inline void modify_fa(int &p,int l,int r,int x,int v){
	
	tr[++cnt]=tr[p];
	p=cnt;
	
	if(l==r){
		tr[p].fa=v;
		return;
	}
	
	if(x<=l+r>>1)
		modify_fa(tr[p].l,l,l+r>>1,x,v);
	else
		modify_fa(tr[p].r,(l+r>>1)+1,r,x,v);
}
inline void modify_dep(int &p,int l,int r,int x,int v){
	
	tr[++cnt]=tr[p];
	p=cnt;
	
	if(l==r){
		tr[p].dep=v;
		return;
	}
	
	if(x<=l+r>>1)
		modify_dep(tr[p].l,l,l+r>>1,x,v);
	else
		modify_dep(tr[p].r,(l+r>>1)+1,r,x,v);
}

inline int fa(int p,int l,int r,int x){
	
	if(l==r)
		return p;
	
	if(x<=l+r>>1)
		return fa(tr[p].l,l,l+r>>1,x);
	else
		return fa(tr[p].r,(l+r>>1)+1,r,x);
}

inline int fidfa(int k,int x){
	int fax=fa(root[k],1,n,x);
	if(x==tr[fax].fa)
		return fax;
	return fidfa(k,tr[fax].fa);
}

inline void hb(int k,int x,int y){
	
	int fax=fidfa(k,x);
	int fay=fidfa(k,y);
	
	if(tr[fax].fa!=tr[fay].fa){
		
		if(tr[fax].dep<tr[fay].dep)
			swap(fax,fay);
		
		modify_fa(root[k],1,n,tr[fay].fa,tr[fax].fa);
		modify_dep(root[k],1,n,tr[fax].fa,tr[fay].dep+(tr[fax].dep==tr[fay].dep));
	}
		
	return;
}

int main(){

	scanf("%d%d",&n,&m);
	
	build(root[0],1,n);
	
	for(int i=1,op,a,b;i<=m;i++){
		
		scanf("%d%d",&op,&a);
		
		root[i]=root[i-1];
			
		if(op==1){
			scanf("%d",&b);
			hb(i,a,b);
		}
		else if(op==2)
			root[i]=root[a];
		else{
			scanf("%d",&b);
			
			int faa=fidfa(i,a);
			int fab=fidfa(i,b);
			
			printf("%d\n",(tr[faa].fa==tr[fab].fa));
			root[i]=root[i-1];
		}
		
	}
	return 0;
}