调了很久，但仍然tle qaq

不吸氧58，吸了之后仍然只有88

求助dalao，感谢！

评测记录

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n, m, tot, root[N];
struct SegmentTree { int lc, rc, val, dep;} tree[N << 5];

inline int read()
{
    register int s = 0, w = 1;
    register char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')
    {
        s *= 10;
        s += ch;
        s -= '0';
        ch = getchar();
    }
    return s * w;
}

int build(int l, int r)
{
    int p = ++ tot;
    if (l == r) { tree[p].val = l, tree[p].dep = 1; return p;}
    
    int mid = l + r >> 1;
    tree[p].lc = build(l, mid);
    tree[p].rc = build(mid + 1, r);
    return p;
}

int insert(int now, int l, int r, int x, int value)
{
    int p = ++ tot;
    tree[p] = tree[now];
    if (l == r) { tree[p].val = value, tree[p].dep = tree[now].dep; return p;}
    int mid = l + r >> 1;
    if (x <= mid) tree[p].lc = insert(tree[now].lc, l, mid, x, value);
    else tree[p].rc = insert(tree[now].rc, mid + 1, r, x, value);
    return p;
}

int query(int p, int l, int r, int x)
{
    if (l == r) return p;
    
    int mid = l + r >> 1;
    if (x <= mid) return query(tree[p].lc, l, mid, x);
    else return query(tree[p].rc, mid + 1, r, x);
}

int find(int rt, int x)
{
    int k = query(rt, 1, n, x);
    
    if (tree[k].val == x) return k;
    return find(rt, tree[k].val);
}

int main()
{
    n = read(), m = read();
    root[0] = build(1, n);
    
    //int x = 0;
    for (int i = 1; i <= m; ++i)
    {
        root[i] = root[i - 1];
        
        int opt = read();
        if (opt == 1)
        {
            int a = read(), b = read();
            //a ^= x, b ^= x;
            int aa = find(root[i], a), bb = find(root[i], b);
            //int aa = query(root[i], 1, n, a_), bb = query(root[i], 1, n, b_);
            //cout << aa << ' ' << bb << endl;
            if (tree[aa].val == tree[bb].val) continue;
            if (tree[aa].dep > tree[bb].dep) swap(aa, bb);
            if (tree[aa].dep == tree[bb].dep) ++ tree[bb].dep;
            root[i] = insert(root[i], 1, n, tree[aa].val, tree[bb].val);
        }
        else if (opt == 2)
        {
            int k = read();
            //k ^= x;
            root[i] = root[k];
        }
        else
        {
            int a = read(), b = read();
            //a ^= x, b ^= x;
            int a_ = find(root[i], a), b_ = find(root[i], b);
            //cout << a_ << ' ' << b_ << endl;
            if (a_ == b_) puts("1");
            else puts("0");
            //x = (a == b);
        }
        
        
    }
    return 0;
}