rt，卡了20min还是96pts，求助！

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll rd(){
   ll x = 0, f = 1; char c = getchar();
   while(! isdigit(c)){if(c == '-')f = - f; c = getchar();}
   while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
   return x * f;
}

const int N = 1e5 + 5;
int n, m;

// namespace __union{
    int rt[N * 40], ls[N * 40], rs[N * 40], ff[N * 40], dep[N * 40], nd;
    void bld(int &x, int l, int r){
        x = ++nd; if(l == r)return ff[x] = l, void();
        int mid = l + r >> 1;
        bld(ls[x], l, mid), bld(rs[x], mid + 1, r);
    }
    void merge(int las, int &x, int l, int r, int pos, int fa){
        ls[x = ++nd] = ls[las]; rs[x] = rs[las];
        if(l == r)return ff[x] = fa, dep[x] = dep[las], void();
        int mid = l + r >> 1;
        if(pos <= mid)merge(ls[las], ls[x], l, mid, pos, fa);
        else merge(rs[las], rs[x], mid + 1, r, pos, fa);
    }
    void upd(int x, int l, int r, int pos){
        if(l == r)return ++dep[x], void();
        int mid = l + r >> 1;
        if(pos <= mid)upd(ls[x], l, mid, pos);
        else upd(rs[x], mid + 1, r, pos);
    }
    int qry(int x, int l, int r, int pos){
        if(l == r)return x; int mid = l + r >> 1;
        if(pos <= mid)return qry(ls[x], l, mid, pos);
        return qry(rs[x], mid + 1, r, pos);
    }
    int fd(int pos, int ver){
        int nw = qry(ver, 1, n, pos);
        return ff[nw] == pos ? nw : fd(ff[nw], ver);
    }
// }
// using namespace __union;

signed main(){
    // freopen("P3402_4.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    n = rd(), m = rd();
    bld(rt[0], 1, n);
    for(int i = 1, o, x, y; i <= m; ++i){
        o = rd(), x = rd();
        if(o == 2)rt[i] = rt[x];
        else if(o ^ 3){
            rt[i] = rt[i - 1];
            y = rd(); x = fd(x, rt[i]); y = fd(y, rt[i]);
            if(ff[x] ^ ff[y]){
                if(dep[x] > dep[y])swap(x, y);
                merge(rt[i - 1], rt[i], 1, n, ff[x], ff[y]);
                if(dep[x] == dep[y])upd(rt[i], 1, n, ff[y]);
            }
        }
        else{
            rt[i] = rt[i - 1];
            y = rd(); x = fd(x, rt[i]); y = fd(y, rt[i]);
            puts(ff[x] == ff[y] ? "1" : "0");
        }
    }
    return 0;
}