我开了两个可持久化线段树，一个用来维护fa,另一个用来维护子树大小，但是T了3个点

是做法假了吗。。。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
inline int read()
{
	int ans=0;char ch=getchar();
	while((ch>'9')||(ch<'0'))ch=getchar();
	while((ch>='0')&&(ch<='9'))ans=ans*10+ch-'0',ch=getchar();
	return ans;
}
struct Segment{int ls,rs,val;}t[3200001],t2[3200001];
int root[200001],n,m,cnt,cnt2;
int build(int l,int r)
{
	int mid=l+((r-l)>>1),nw=++cnt;
	if(l==r)t[nw].val=l;
	else t[nw].ls=build(l,mid),t[nw].rs=build(mid+1,r);
	return nw;
}
int build2(int l,int r)
{
	int mid=l+((r-l)>>1),nw=++cnt2;
	if(l==r)t2[nw].val=1;
	else t2[nw].ls=build2(l,mid),t2[nw].rs=build2(mid+1,r);
	return nw;
}
int change(int from,int l,int r,int x,int y)
{
	int nw=++cnt,mid=l+((r-l)>>1);
	if(l==r){t[nw].val=y;return nw;}
	if(x<=mid)t[nw].rs=t[from].rs,t[nw].ls=change(t[from].ls,l,mid,x,y);
	else t[nw].ls=t[from].ls,t[nw].rs=change(t[from].rs,mid+1,r,x,y);
	return nw;
}
int change2(int from,int l,int r,int x,int y)
{
	int nw=++cnt2,mid=l+((r-l)>>1);
	if(l==r){t2[nw].val+=y;return nw;}
	if(x<=mid)t2[nw].rs=t2[from].rs,t2[nw].ls=change2(t2[from].ls,l,mid,x,y);
	else t2[nw].ls=t2[from].ls,t2[nw].rs=change2(t2[from].rs,mid+1,r,x,y);
	return nw;
}
int ask(int nw,int l,int r,int x)
{
	int mid=l+((r-l)>>1);
	if(l==r)return t[nw].val;
	if(x<=mid)return ask(t[nw].ls,l,mid,x);
	return ask(t[nw].rs,mid+1,r,x);
}
int ask2(int nw,int l,int r,int x)
{
	int mid=l+((r-l)>>1);
	if(l==r)return t2[nw].val;
	if(x<=mid)return ask2(t2[nw].ls,l,mid,x);
	return ask2(t2[nw].rs,mid+1,r,x);
}
int find(int nw,int x)
{
	int k=ask(nw,1,n,x);
	return k==x?x:find(nw,k);
}
void merge(int rt,int nw,int x,int y)
{
	x=find(rt,x),y=find(rt,y);
	int sizx=ask2(rt,1,n,x),sizy=ask2(rt,1,n,y);
	if(sizx>sizy)
	{
		root[nw]=change(rt,1,n,y,x);
		change2(rt,1,n,x,sizy);
	}
	else
	{
		root[nw]=change(rt,1,n,x,y);
		change2(rt,1,n,y,sizx);
	}
}
signed main()
{
	n=read(),m=read();int opt,x,y;
	root[0]=build(1,n);
	for(int i=1;i<=m;++i)
	{
		opt=read();
		switch(opt)
		{
			case 1:x=read(),y=read(),merge(root[i-1],i,x,y);break;
			case 2:x=read(),root[i]=root[x];break;
			case 3:x=read(),y=read(),root[i]=root[i-1];cout<<(find(root[i],x)==find(root[i],y))<<"\n";break;
		}
	}
	return 0;
}