数组开小时只有 52 pts，改了一下后就改不动了只有 68 pts

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<cstdlib>
#include<set>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
const int MAXN=1e6+10;
int n,m;
struct tree
{
	int dep,fa;
	int ch[2];
}tr[MAXN*30];
int root[MAXN],tot=0;//节点个数 
int last;//记录本次操作前线段树上的总结点数 
void build(int &k,int l,int r)
{
	k=++tot;
	if(l==r)
	{
		tr[k].fa=l,tr[k].dep=1;
		return ;
	}
	int mid=l+r>>1;
	build(tr[k].ch[0],l,mid),build(tr[k].ch[1],mid+1,r);
}
int find(int k,int l,int r,int x,int id)
{
	if(l==r)
	{
		if(tr[k].fa==l)//说明找到了k节点的祖先 
			return k;
		return find(root[id],1,n,tr[k].fa,id);
	}
	int mid=l+r>>1;
	if(x<=mid)
		return find(tr[k].ch[0],l,mid,x,id);
	else
		return find(tr[k].ch[1],mid+1,r,x,id);
}
void modefy(int &k,int q,int l,int r,int x,int f)
{
	k=++tot,tr[k]=tr[q];
	if(l==r)
	{
		tr[k].fa=f;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid)
		modefy(tr[k].ch[0],tr[q].ch[0],l,mid,x,f);
	else
		modefy(tr[k].ch[1],tr[q].ch[1],mid+1,r,x,f);
}
void merge(int &k,int q,int l,int r,int x)//按深度合并 
{
	if(k<=last)
		k=++tot,tr[k]=tr[q];
	if(l==r)
	{
		tr[k].dep++;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid)
		merge(tr[k].ch[0],tr[q].ch[0],l,mid,x);
	else
		merge(tr[k].ch[1],tr[q].ch[1],mid+1,r,x);
}
int main()
{
	n=read(),m=read();
	build(root[0],1,n);
	last=tot;
	for(int i=1;i<=m;i++)
	{
		int op=read(),x,y;
		if(op==1)
		{
			x=read(),y=read();
			root[i]=root[i-1];
			x=find(root[i],1,n,x,i),y=find(root[i],1,n,y,i);
			if(tr[x].fa==tr[y].fa)
				continue;
			if(tr[x].dep<tr[y].dep)
				swap(tr[x],tr[y]);
			modefy(root[i],root[i-1],1,n,tr[y].fa,tr[x].fa);//将y的子树合并到x上
			if(tr[x].dep==tr[y].dep)
				merge(root[i],root[i-1],1,n,tr[x].fa);
			last=tot;
		}
		if(op==2)
		{
			x=read();
			root[i]=root[x];
		}
		if(op==3)
		{
			x=read(),y=read();
			root[i]=root[i-1];
			x=find(root[i],1,n,x,i),y=find(root[i],1,n,y,i);
			if(tr[x].fa==tr[y].fa)
				printf("1\n");
			else
				printf("0\n");
		}
	}
	return 0;
}