rt,代码如下

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int MAXN=2e5+10;
struct node{
	int ls,rs,size,fa;
}tree[MAXN<<5];
int root[MAXN];
int tot=0;
int a[MAXN];
inline int create(int p)
{
	++tot;
	tree[tot]=tree[p];
	return tot;
}
inline int ask(int p,int l,int r,int x)
{
	if(l==r)
	return tree[p].fa;
	int mid=(l+r)>>1;
	if(x<=mid)
	return ask(tree[p].ls,l,mid,x);
	else
	return ask(tree[p].rs,mid+1,r,x);
}
inline int find(int p,int x)
{
	int f=ask(p,1,n,x);
	if(x==f)
	return x;
	return find(p,f);
}
inline int query(int p,int l,int r,int x)
{
	if(l==r)
	return tree[p].size;
	int mid=(l+r)>>1;
	if(x<=mid)
	return query(p,l,mid,x);
	else
	return query(p,mid+1,r,x);
}
inline int modify(int p,int l,int r,int x,int y)
{
	p=create(p);
	if(l==r&&l==x)
	tree[p].fa=y;
	else
	{
		int mid=(l+r)>>1;
		if(x<=mid)
		tree[p].ls=modify(tree[p].ls,l,mid,x,y);
		else
		tree[p].rs=modify(tree[p].rs,mid+1,r,x,y);
	}
	return p;
}
inline int build(int p,int l,int r)
{
	p=create(p);
	if(l==r)
	{
		tree[p].fa=l;
		tree[p].size=1;
		return p;
	}
	int mid=(l+r)>>1;
	tree[p].ls=build(tree[p].ls,l,mid);
	tree[p].rs=build(tree[p].rs,mid+1,r);
	return p;
}
inline int add(int p,int l,int r,int x,int v)
{
	p=create(p);
	if(l==r&&l==x)
		tree[p].size+=v;
	else
	{
		int mid=(l+r)>>1;
		if(x<=mid)
		tree[p].ls=modify(tree[p].ls,l,mid,x,v);
		else
		tree[p].rs=modify(tree[p].rs,mid+1,r,x,v);
	}
	return p;
}
signed main()
{
	scanf("%d%d",&n,&m);
	root[0]=build(root[0],1,n);
	int i=1;
	while(m--)
	{
		int opt,a,b,k;
		scanf("%d",&opt);
		if(opt==1)
		{
			scanf("%d%d",&a,&b);
			a=find(root[i-1],a);
			b=find(root[i-1],b);
			int sum1=query(root[i-1],1,n,a),sum2=query(root[i-1],1,n,b);
			if(sum1>sum2)
			{
			swap(a,b);
			swap(sum1,sum2);
			}
			root[i]=modify(root[i-1],1,n,a,b);
			add(root[i],1,n,b,sum1);
		}
		if(opt==2)
		{
			scanf("%d",&k);
			root[i]=root[k];
		}
		if(opt==3)
		{
			scanf("%d%d",&a,&b);
			root[i]=root[i-1];
			if(find(root[i],a)==find(root[i],b))
			printf("1\n");
			else
			printf("0\n");
		}
		i++;
	}
	return 0;
}