我把dep和fa全部扔到一个内存池里，然后修改完按秩合并之后吸氧第五个点从900->400，然后第八个点照T无误，Orz救救孩子吧

https://www.luogu.com.cn/record/44458474

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(nullptr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;

const ll LINF=2e18;
const ll MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int MAXN=200050;

struct node{
	int val;
	int l,r;
}tr[MAXN*80];
int rootfa[MAXN],rootdep[MAXN],cnt=0,n;
inline int read() 
{
	register int x=0,o=0;register char ch=getchar();
	while(ch!='-'&&(ch<'0'||'9'<ch)) ch=getchar();
	if(ch=='-') o=1,ch=getchar();
	while('0'<=ch&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return o?-x:x;
}
void build(int &id,int lb,int rb){
	id=++cnt;
	if(lb>=rb){
		tr[id].val=lb;
		return;
	}
	int mid=(lb+rb)>>1;
	build(tr[id].l,lb,mid);
	build(tr[id].r,mid+1,rb);
}
int query(int id,int x,int lb,int rb){
	if(lb>=rb)return tr[id].val;
	int mid=(lb+rb)>>1;
	if(x<=mid)return query(tr[id].l,x,lb,mid);
	else return query(tr[id].r,x,mid+1,rb);
}
int find(int id,int x){
	int fath=query(id,x,1,n);
	return fath==x?x:find(id,fath);
}
void modify(int &id,int pre,int x,int val,int lb,int rb){
	id=++cnt;
	tr[id].l=tr[pre].l;
	tr[id].r=tr[pre].r;
	if(lb>=rb){
		tr[id].val=val;
		return;
	}
	int mid=(lb+rb)>>1;
	if(x<=mid)modify(tr[id].l,tr[pre].l,x,val,lb,mid);
	else modify(tr[id].r,tr[pre].r,x,val,mid+1,rb);
}
void add(int id,int x,int lb,int rb){
	if(lb>=rb){
		tr[id].val++;
		return;
	}
	int mid=(lb+rb)>>1;
	if(x<=mid)add(tr[id].l,x,lb,mid);
	else add(tr[id].r,x,mid+1,rb);
}
void merge(int now,int pre,int x,int y){
	int fax=find(rootfa[pre],x),fay=find(rootfa[pre],y);
	if(fax==fay){
		rootfa[now]=rootfa[pre];
		rootdep[now]=rootdep[pre];
		return;
	}
	int depx=query(rootdep[pre],fax,1,n),depy=query(rootdep[pre],fay,1,n);
	if(depx!=depy){
		if(depx>depy){
			swap(fax,fay);
			swap(depx,depy);
		}
		modify(rootfa[now],rootfa[pre],fax,fay,1,n);
		//modify(rootdep[now],rootdep[pre],fax,depy,1,n);
	}else{
		modify(rootfa[now],rootfa[pre],fax,fay,1,n);
		modify(rootdep[now],rootdep[pre],fay,depy+1,1,n);
	}
}
void solve(int T){
	int m;
	n=read(),m=read();
	build(rootfa[0],1,n);
	int o,x,y;
	for(int i=1;i<=m;i++){
		o=read();
		if(o==1){
			x=read(),y=read();
			merge(i,i-1,x,y);
		}else if(o==2){
			x=read();
			rootfa[i]=rootfa[x];
			rootdep[i]=rootdep[x];
		}else if(o==3){
			x=read(),y=read();
			rootfa[i]=rootfa[i-1];
			rootdep[i]=rootdep[i-1];
			int fax=find(rootfa[i],x),fay=find(rootfa[i],y);
			if(fax==fay)puts("1");
			else puts("0");
			//printf("%d\n",find(rootfa[i],x)==find(rootfa[i],y)?1:0);
		}
	}
}
signed main(){
	//IOS;
	int t=1;
	//scanf("%d",&t);
	for(int i=1;i<=t;i++){
		solve(i);
	}
}