#2#5 1.2s，#16 1.05s

常数太大了还是我哪里写假了/kk

#include<iostream>
using namespace std;
int rt[200005],lson[3800005],rson[3800005],fa[3800005],deep[3800005],tot=0;
int n,m;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')
        {
            t=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*t;
}
void build(int l,int r,int i)
{
	tot++;
	if(l==r)
	{
		fa[i]=l;
		deep[i]=1;
	}
	else
	{
		int mid=(l+r)>>1;
		lson[i]=tot+1;
		build(l,mid,lson[i]);
		rson[i]=tot+1;
		build(mid+1,r,rson[i]);
	}
}
void modify(int l,int r,int q,int k,int i)
{
	tot++;
	int id=tot;
	if(l==r)
	{
		fa[id]=k;
		return;
	}
	lson[id]=lson[i];
	rson[id]=rson[i];
	int mid=(l+r)>>1;
	if(q<=mid)
	{
		lson[id]=tot+1;
		modify(l,mid,q,k,lson[i]);
	}
	else
	{
		rson[id]=tot+1;
		modify(mid+1,r,q,k,rson[i]);
	}
}
void modify2(int l,int r,int q,int k,int i)
{
	if(l==r)
	{
		deep[i]=k;
		return;
	}
	int mid=(l+r)>>1;
	if(q<=mid)
	{
		modify2(l,mid,q,k,lson[i]);
	}
	else
	{
		modify2(mid+1,r,q,k,rson[i]);
	}
}
int ask(int l,int r,int q,int i)
{
	if(q<l||r<q)
	{
		return 0;
	}
	if(l==r)
	{
		return i;
	}
	int mid=(l+r)>>1;
	return ask(l,mid,q,lson[i])+ask(mid+1,r,q,rson[i]);
}
int find(int x,int now)
{
	int fid=ask(1,n,x,rt[now]);
	if(fa[fid]==x)
	{
		return fid;
	}
	return find(fa[fid],now);
}
inline void con(int x,int y ,int i)
{
	int faid=find(x,i),fbid=find(y,i);
	int faa=fa[faid];
	int da=deep[faid];
	int fab=fa[fbid];
	int db=deep[fbid];
	rt[i]=tot+1;
	if(da>db)
	{
		modify(1,n,fab,faa,rt[i-1]);
	}
	else if(db>da)
	{
		modify(1,n,faa,fab,rt[i-1]);
	}
	else
	{
		modify(1,n,fab,faa,rt[i-1]);
		deep[faid]++;
		//modify2(1,n,faa,da+1,rt[i]);
	}
}
int main()
{
	n=read(),m=read();
	rt[0]=1;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	build(1,n,1);
	for(int i=1;i<=m;i++)
	{
		int opt,x,y;
		opt=read(),x=read();
		if(opt==1)
		{
			rt[i]=rt[i-1];
			y=read();
			con(x,y,i);
		}
		if(opt==2)
		{
			rt[i]=rt[x];
		}
		if(opt==3)
		{
			rt[i]=rt[i-1];
			y=read();
			if(find(x,i)==find(y,i))
			{
				putchar('1');
			}
			else
			{
				putchar('0');
			}
			putchar('\n');
		}
	}
	return 0;
}

悬一关