rt,WA on #7~#9 样例能过

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
const int N=2e5+1;
int id,n,m;

struct tree //主席树
{
	int tot,root[N],x[N<<5],y[N<<5];
	void build(int &rt,int l,int r,bool v) {
		rt=(++tot); if (l==r) x[rt]=v?l:1;
		else build(x[rt],l,mid,v),build(y[rt],mid+1,r,v);
	}
	void update(int &rt,int p,int l,int r,int pos,int val)
	{
		rt=(++tot); if (l==r) return x[rt]=val,void();
		if (pos<=mid) update(x[rt],x[p],l,mid,pos,val),y[rt]=y[p];
		else update(y[rt],y[p],mid+1,r,pos,val),x[rt]=x[p];
	}
	int query(int rt,int l,int r,int pos)
	{
		if (l==r) return x[rt];
		if (pos<=mid) return query(x[rt],l,mid,pos);
		else return query(y[rt],mid+1,r,pos);
	}
}A,B;

int find(int x) {
	int f=A.query(A.root[id-1],1,n,x);
	return x==f?x:find(f);
}
void merge(int x,int y)
{
	int fx=find(x),fy=find(y);
	int sx=B.query(B.root[id-1],1,n,fx);
	int sy=B.query(B.root[id-1],1,n,fy);
	if (fx==fy) return; if (sx>sy) swap(fx,fy);
	A.update(A.root[id],A.root[id-1],1,n,fx,fy);
	B.update(B.root[id],B.root[id-1],1,n,fy,sx+sy);
}
int main()
{
	int op,x,y;
	scanf("%d%d",&n,&m);
	A.build(A.root[0],1,n,1);
	B.build(B.root[0],1,n,0);
	for (id=1;id<=m;id++)
	{
		scanf("%d%d",&op,&x);
		if (op==1) {
			scanf("%d",&y);
			merge(x,y);
		}if (op==2) {
			A.root[id]=A.root[x];
			B.root[id]=B.root[x];
		}if (op==3) {
			A.root[id]=A.root[id-1],B.root[id]=B.root[id-1];
			scanf("%d",&y),printf("%d\n",find(x)==find(y));
		}
	}
	return 0;
}