RT #2#5#13 TLE 1.20s

萌新第一次写按深度合并并查集，可能假了/kk

#include <bits/stdc++.h>
using namespace std;
#define M 200005 // 2e5
int n,m,a[M],rt[M],op,ox,oy,ou,oa,ob,ov,ct,fa[M],lst;
int t[M*20],ls[M*20],rs[M*20],cntp;
void read(int &nd) {
    nd=0;
    register char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch<='9'&&ch>='0') nd=(nd<<3)+(nd<<1)+ch-'0',ch=getchar();
}
int buildt(int L,int R) {
    int res=++cntp,mid=(L+R)/2;
    if(L==R) {
        t[res]=L;
        return res;
    }
    ls[res]=buildt(L,mid);
    rs[res]=buildt(mid+1,R);
    return res;
}
int Query(int i,int L,int R,int wl) { // 主席树查询
    if(L==R) return t[i];
    int mid=(L+R)/2;
    if(mid>=wl) return Query(ls[i],L,mid,wl);
    return Query(rs[i],mid+1,R,wl);
}
int Change(int i,int L,int R,int wl,int kv) { // 主席树修改
    int res=++cntp,mid=(L+R)/2;
    if(L==R) {
        t[res]=kv;
        return res;
    }
    ls[res]=ls[i],rs[res]=rs[i];
    if(mid>=wl) ls[res]=Change(ls[res],L,mid,wl,kv);
    else rs[res]=Change(rs[res],mid+1,R,wl,kv);
    return res;
}
int getfa(int x) { // 暴力找根
    int ffa;
    while(1) {
        ffa=Query(rt[lst],1,n,x);
        if(ffa==x) return x;
        else x=ffa,ct++;
    } return x;
}
signed main() {
    read(n),read(m);
    rt[0]=buildt(1,n);
    for(int i=1;i<=m;i++) {
        read(op),read(ox);
        if(op==2) {
            lst=ox;
            rt[i]=rt[lst];
        } else if(op==1) {
            read(oy),lst=i-1;
            ct=0,ou=getfa(ox),oa=ct;
            ct=0,ov=getfa(oy),ob=ct;
            if(ou==ov) {
                rt[i]=rt[lst];
                continue;
            }
            if(oa<ob) rt[i]=Change(rt[lst],1,n,ou,ov);
            else rt[i]=Change(rt[lst],1,n,ov,ou); // 按深度合并
        } else if(op==3) {
            read(oy),lst=i-1,rt[i]=rt[lst];
            ou=getfa(ox),ov=getfa(oy);
            printf("%d\n",(ou==ov?1:0));
        }
    }
    return 0;
}