rt, TLE on #14

#include<bits/stdc++.h>
using namespace std;
#define fr(i,l,r) for(int i(l);i<=r;i++)
template<typename T>inline T rd(T&a){
    #define gc getchar
    #define dg(x) (x>='0'&&x<='9')
    char c=gc();T x=0,f=1;
    for(;!dg(c);c=gc())if(c=='-')f=-1;
    for(;dg(c);c=gc())x=(x<<1)+(x<<3)+c-48;
    return a=f*x;
}template<typename T,typename...V>inline void rd(T&x,V&...v){rd(x),rd(v...);}
const int N=2e5+3;
int n,m,op,x,y;

struct persistent_arr {
#define mid ((l+r)>>1)
    int tot,rt[N],ls[N<<7],rs[N<<7],val[N<<7];
    void build(int&p,int l,int r,int v){
        p=++tot;
        if(l==r)return val[p]=~v?v:l,void();
        build(ls[p],l,mid,v),build(rs[p],mid+1,r,v);
    }
    void modify(int o,int&p,int l,int r,int k,int x){
        p=++tot,ls[p]=ls[o],rs[p]=rs[o],val[p]=val[o];
        if(l==r)return val[p]=x,void();
        k>mid?modify(rs[o],rs[p],mid+1,r,k,x):modify(ls[o],ls[p],l,mid,k,x);
    }void sett(int ver,int k,int x){modify(rt[ver-1],rt[ver],1,n,k,x);}
    int ask(int p,int l,int r,int k){
        if(l==r)return val[p];
        return k>mid?ask(rs[p],mid+1,r,k):ask(ls[p],l,mid,k);
    }int at(int ver,int k){return ask(rt[ver],1,n,k);}
}fa,dep;

struct persistent_dsu {
    inline int find(int ver,int x){
        int f=fa.at(ver,x);
        return x==f?x:find(ver,f);
    }
    void merge(int ver,int x,int y){
        int fx=find(ver,x),fy=find(ver,y);
        if(fx==fy)return;
        int dx=dep.at(ver,x),dy=dep.at(ver,y);
        if(dx>dy)swap(x,y),swap(fx,fy),swap(dx,dy);
        fa.sett(ver,fx,fy);
        if(dx==dy)dep.sett(ver,fy,dy+1);
    }
}dsu;

int main(){
    // freopen("P3402_14.in","r",stdin);
    // freopen("P3402_14.ans","w",stdout);
    rd(n,m);fa.build(fa.rt[0],1,n,-1),dep.build(dep.rt[0],1,n,1);
    fr(i,1,m){
        rd(op,x),fa.rt[i]=fa.rt[i-1],dep.rt[i]=dep.rt[i-1];
        if(op==1)dsu.merge(i,x,rd(y));
        else if(op&1)cout<<(dsu.find(i,x)==dsu.find(i,rd(y)))<<'\n';
        else fa.rt[i]=fa.rt[x],dep.rt[i]=dep.rt[x];
    }return 0;
}