#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
struct Node {
    int l, r, ls, rs, siz, fa;
    inline int mid(void) { return (l + r) >> 1; }
} tr[N << 5];
int n, m, opt, x, y, mem, rt, root[N << 1];
inline int clone(int p) {
    return tr[++mem] = tr[p], mem;
}
inline void build(int &p, int l, int r) {
    p = ++mem, tr[p] = {l, r};
    if (l == r) {
        tr[p].siz = 1, tr[p].fa = l;
    } else {
        const int m = (l + r) >> 1;
        build(tr[p].ls, l, m), build(tr[p].rs, m + 1, r);
    }
}
inline int add_siz(int p, int x, int v) {
    p = clone(p);
    if (tr[p].l == tr[p].r) {
        tr[p].siz += v;
    } else {
        if (x <= tr[p].mid()) {
            tr[p].ls = add_siz(tr[p].ls, x, v);
        } else {
            tr[p].rs = add_siz(tr[p].rs, x, v);
        }
    }
    return p;
}
inline int query_siz(int p, int x) {
    if (tr[p].l == tr[p].r) return tr[p].siz;
    return query_siz(x <= tr[p].mid() ? tr[p].ls : tr[p].rs, x);
}
inline int set_fa(int p, int x, int v) {
    p = clone(p);
    if (tr[p].l == tr[p].r) {
        tr[p].fa = v;
    } else {
        if (x <= tr[p].mid()) {
            tr[p].ls = set_fa(tr[p].ls, x, v);
        } else {
            tr[p].rs = set_fa(tr[p].rs, x, v);
        }
    }
    return p;
}
inline int query_fa(int p, int x) {
    if (tr[p].l == tr[p].r) return tr[p].fa;
    return query_fa(x <= tr[p].mid() ? tr[p].ls : tr[p].rs, x);
}
inline int find(int x, int rt) {
    int fx = query_fa(rt, x);
    return fx == x ? x : find(fx, rt);
}
inline void merge(int x, int y, int from, int &to) {
    int fx = find(x, from), fy = find(y, from);
    if (fx == fy) {
        return to = from, void();
    }
    int sx = query_siz(from, fx);
    int sy = query_siz(from, fy);
    if (sx < sy) std::swap(fx, fy);
    to = set_fa(from, fy, fx), to = add_siz(to, fx, sy);
}
inline bool same(int x, int y, int rt) {
    return find(x, rt) == find(y, rt);
}
int main(int argc, char const *argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m, build(root[0], 1, n);
    for (int i = 1; i <= m; i++) {
        cin >> opt >> x;
        if (opt == 1) {
            cin >> y, merge(x, y, root[i - 1], root[i]);
        } else if (opt == 2) {
            root[i] = rt = root[x];
        } else {
            cin >> y, root[i] = root[i - 1];
            cout << same(x, y, root[i]) << '\n';
        }
    }
    return 0;
}

rt，这份代码使用了启发式合并的并查集，TLE on #2,5,6,11,14 想问一下对于可持久化并查集，启发式合并和按秩合并有什么区别吗？下载数据在本地大概要跑 3s.