rt，可持久化数组部分应该是没问题的，大概率错在merge或者find，谢谢聚聚。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <functional>
#include <map>
#include <queue>
#include <vector>
#include <utility>

#define ed end()
#define bg begin()
#define mp make_pair
#define pb push_back
#define all(x) x.bg, x.ed
#define newline puts("")
#define si(x) ((int)x.size())
#define rep(i, n) for(register int i = 1; i <= n; ++i)
#define rrep(i, n) for(register int i = 0; i < n; ++i)
#define srep(i, s, t) for(register int i = s; i <= t; ++i)
#define drep(i, s, t) for(register int i = t; i >= s; --i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INF_ll = 1ll * INF * INF;
const int MOD = 1e9 + 7;
const double eps = 1e-7;

int n, m;

struct node
{
    int l, r, val;
} tr[MAX << 8];//此时的线段树维护了两个可持久化数组。

int rtf[MAX], rtd[MAX];//使用两个不同的数组来分别存父亲和深度树

int cnt;
int tot;//用来初始化并查集数组

inline int clone(int p)
{
    tr[++cnt] = tr[p];
    return cnt;
}

inline int r(){
    char c = getchar();int x = 0,fh = 0;
    while(c < '0' || c > '9'){fh |= c == '-';c = getchar();}
    while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}
    return fh?-x:x;
}

//只有并查集数组要初始化为自身，树高数组一开始都为零。
int build(int p, int s, int e)
{
    p = ++cnt;
    if(s == e)
    {
        tr[p].val = ++tot;
        return cnt;
    }
    int mid = s + ((e - s) >> 1);
    tr[p].l = build(tr[p].l, s, mid);
    tr[p].r = build(tr[p].r, mid + 1, e);
    return p;
}

int modify(int p, int s, int e, int pos, int nval)
{
    p = clone(p);
    if(s == e)
    {
        tr[p].val = nval;
        return p;
    }
    int mid = s + ((e - s) >> 1);
    if(pos <= mid) tr[p].l = modify(tr[p].l, s, mid, pos, nval);
    else tr[p].r = modify(tr[p].r, mid + 1, e, pos, nval);
    return p;
}

int query(int p, int s, int e, int pos)
{
    if(s == e) return tr[p].val;
    int mid = s + ((e - s) >> 1);
    if(pos <= mid) return query(tr[p].l, s, mid, pos);
    else return query(tr[p].r, mid + 1, e, pos);
}

inline int find(int ver, int x)
{
    int fx = query(rtf[ver], 1, n, x);
    return (fx == x) ? x : find(ver, fx);
}

void merge(int ver, int x, int y)
{
    int fx = find(ver - 1, x);
    int fy = find(ver - 1, y);
    if(fx == fy)
    {
        rtf[ver] = rtf[ver - 1];
        rtd[ver] = rtd[ver - 1];
    }
    else
    {
        int depx = query(rtd[ver - 1], 1, n, x);
        int depy = query(rtd[ver - 1], 1, n, y);
        if(depx > depy)
        {
            rtf[ver] = modify(rtf[ver - 1], 1, n, y, x);
            rtd[ver] = rtd[ver - 1];
        }
        else if(depx < depy)
        {
            rtf[ver] = modify(rtf[ver - 1], 1, n, x, y);
            rtd[ver] = rtd[ver - 1];
        }
        else
        {
            rtf[ver] = modify(rtf[ver - 1], 1, n, x, y);
            rtd[ver] = modify(rtd[ver - 1], 1, n, y, depy + 1);
        }
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("Slove.in","r", stdin);
        freopen("Slove.out","w", stdout);
    #endif
    n = r(), m = r();
    rtf[0] = build(0, 1, n);
    rep(i, m)
    {
        int op;
        op = r();
        if(1 == op)
        {
            int a, b;
            a = r(), b = r();
            merge(i, a, b);
            // int fa = find(i, a), fb = find(i, b);
            // printf("%c\n", (fa == fb) ? 'Y' : 'N');
        }
        else if(2 == op)
        {
            int k;
            k = r();
            rtf[i] = rtf[k];
            rtd[i] = rtd[k]; 
        }
        if(3 == op)
        {
            int a, b;
            a = r(), b = r();
            rtf[i] = rtf[i - 1];
            rtd[i] = rtd[i - 1];
            int fa = find(i, a), fb = find(i, b);
            // printf("f[%d] = %d f[%d] = %d\n", a, fa, b, fb);
            printf("%d\n", (fa == fb) ? 1 : 0);
        }
    }
    return 0;
}