76pts 有WA有TLE

#include<bits/stdc++.h>
using namespace std;
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 N=1e5+10;
int n,m;

	int root[N],tot;
	struct Node{
		int l,r,fa,dep;
	}t[N*24];
	int build(int left,int right) {
		int p=++tot;
		if(left==right) {
			t[p].fa=left;
			t[p].dep=1;
			return p;
		}
		int mid=(left+right)>>1;
		t[p].l=build(left,mid);
		t[p].r=build(mid+1,right);
		return p;
	}
	void merge(int rt,int &p,int left,int right,int x,int Fa) {
		p=++tot;
		t[p]=t[rt];
		if(left==right) {
			t[p].dep=t[rt].dep;
			t[p].fa=Fa;
			return ;
		}
		int mid=(left+right)>>1;
		if(x<=mid) merge(t[rt].l,t[p].l,left,mid,x,Fa);
		else merge(t[rt].r,t[p].r,mid+1,right,x,Fa);
	}
	void update(int rt,int left,int right,int x) {
		if(left==right) {
			t[rt].dep++;
			return ;
		}
		int mid=(left+right)>>1;
		if(x<=mid) update(t[rt].l,left,mid,x);
		else update(t[rt].r,mid+1,right,x);
	}
	int query(int rt,int left,int right,int x) {
		if(left==right) return rt;
		int mid=(left+right)>>1;
		if(x<=mid) return query(t[rt].l,left,mid,x);
		else return query(t[rt].r,mid+1,right,x);
	}
	int find(int rt,int pos) {
		int now=query(rt,1,n,pos);
		if(t[now].fa==pos) return now;
		return find(rt,t[now].fa);
	}

int main() {
//	freopen("Cheng.in","r",stdin); 
//	freopen("Cheng.out","w",stdout);
	n=read(); m=read();
	root[0]=build(1,n);
	for(int i=1;i<=m;i++) {
		int op=read(),x=read();
		if(op==1) {
			root[i]=root[i-1];
			int y=read();
			int posx=find(root[i],x),posy=find(root[i],y);
			if(t[posx].fa==t[posy].fa) continue;
			if(t[posx].dep>t[posy].dep) swap(posx,posy);
			merge(root[i-1],root[i],1,n,t[posx].fa,t[posy].fa);
			if(t[posx].dep==t[posy].dep) update(root[i],1,n,t[posy].fa);
		}
		if(op==2) 
			root[i]=root[x];
		if(op==3) {
			root[i]=root[i-1];
			int y=read();
			int posx=find(root[i],x),posy=find(root[i],y);
			if(t[posx].fa==t[posy].fa) puts("1");
			else puts("0");
		}
	}
	return 0;
}