（貌似整个代码不能用 $makeroot$ ？是因为是有根树？）

因为是区间操作，所以可以考虑在区间内与区间外的差异

对于操作 $1$ ，可以看作一个生成节点包含了到下一个 $1$ 操作之间长出的节点，那么对于一个操作 $l, r$ ，相当于是在 $l$ 处将当前生成节点及其包含的节点整个移植到它更改后的位置，到 $r + 1$ 时再移植回去，所以可以考虑将一个 $1$ 操作分解为两个操作（一个移植，一个移植回去），故可以将所有操作按端点、时间排序（以及同位置修改操作必定在查询操作前，因为可以先把树建完再查询对结果没有影响），扫描一遍即可

同时，为了方便移植，将每个生成节点看作新建的一个虚点

对于操作 $0$ ，直接在虚点下 $link$ 即可，因为就算已经建了一些对于当前操作不存在的虚点，也不会对答案造成影响

对于操作 $2$ ，无法正面在 $LCT$ 上算出两点的距离，故可考虑差分，得到 $Ans = Sum_x + Sum_y - 2 * Sum_{lca}$ ，其中实点贡献为 $1$ ，虚点贡献为 $0$

对于求 $LCA$ ，先 $access (y)$ ，再在 $access (x)$ 的时候得到的最后一个跳虚边的点即是它们的 $LCA$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 3e05 + 10;

struct QuerySt {
    int pos, time;
    int x, y;

    QuerySt () {}
    QuerySt (int fpos, int ftime, int fx, int fy) :
        pos (fpos), time (ftime), x (fx), y (fy) {}

    bool operator < (const QuerySt& p) const {
        return pos == p.pos ? time < p.time : pos < p.pos;
    }
} ;
QuerySt Query[MAXN];
int que = 0;

int N, M;

int father[MAXN]= {0};
int son[MAXN][2]= {0};
int Sum[MAXN]= {0}, value[MAXN]= {0};

int isroot (int p) {
    return son[father[p]][0] != p && son[father[p]][1] != p;
}
int sonbel (int p) {
    return son[father[p]][1] == p;
}
void pushup (int p) {
    Sum[p] = Sum[son[p][0]] + Sum[son[p][1]] + value[p];
}
void rotate (int p) {
    int fa = father[p], anc = father[fa];
    int s = sonbel (p);
    son[fa][s] = son[p][s ^ 1];
    if (son[fa][s])
        father[son[fa][s]] = fa;
    if (! isroot (fa))
        son[anc][sonbel (fa)] = p;
    father[p] = anc;
    son[p][s ^ 1] = fa, father[fa] = p;
    pushup (fa), pushup (p);
}
void splay (int p) {
    for (int fa = father[p]; ! isroot (p); rotate (p), fa = father[p])
        if (! isroot (fa))
            sonbel (p) == sonbel (fa) ? rotate (fa) : rotate (p);
}
int Access (int p) {
    int tp = 0;
    for ( ; p; tp = p, p = father[p])
        splay (p), son[p][1] = tp, pushup (p);
    return tp;
}
void link (int x, int y) { // 注意此时没有makeroot所以需要注意是将y连到x下
    splay (y);
    father[y] = x;
}
void cut (int x) {
    Access (x), splay (x);
    father[son[x][0]] = 0, son[x][0] = 0;
    pushup (x);
}

int totq = 0;
int ans[MAXN]= {0};
void Solve () {
    sort (Query + 1, Query + que + 1);
    for (int i = 1; i <= que; i ++) {
        int time = Query[i].time;
        int x = Query[i].x, y = Query[i].y;
        if (time > 0) {
            Access (x), splay (x), ans[time] += Sum[x];
            int lca = Access (y);
            splay (y), ans[time] += Sum[y];
            Access (lca), splay (lca), ans[time] -= (Sum[lca] << 1);
        }
        else
            cut (x), link (y, x);
    }
}

int getnum () {
    int num = 0;
    char ch = getchar ();

    while (! isdigit (ch))
        ch = getchar ();
    while (isdigit (ch))
        num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

    return num;
}

int ind[MAXN]= {0};
int liml[MAXN], limr[MAXN];
int nodes = 1;
int main () {
    N = getnum (), M = getnum ();
    int lastr = 1, real = 1;
    ind[1] = Sum[1] = value[1] = 1, liml[1] = 1, limr[1] = N;
    link (1, nodes = lastr = 2);
    for (int i = 1; i <= M; i ++) {
        int opt = getnum ();
        if (opt == 0) {
            int l = getnum (), r = getnum ();
            link (lastr, ind[++ real] = ++ nodes);
            value[nodes] = Sum[nodes] = 1;
            liml[real] = l, limr[real] = r;
        }
        else if (opt == 1) {
            int l = getnum (), r = getnum (), x = getnum ();
            l = max (l, liml[x]), r = min (r, limr[x]);
            if (l > r)
                continue;
            link (lastr, ++ nodes);
            Query[++ que] = QuerySt (l, i - M, nodes, ind[x]); // 由nodes离开link向index[x]
            Query[++ que] = QuerySt (r + 1, i - M, nodes, lastr);
            lastr = nodes;
        }
        else if (opt == 2) {
            int x = getnum (), u = getnum (), v = getnum ();
            Query[++ que] = QuerySt (x, ++ totq, ind[u], ind[v]); // 由index[u]到index[v]的距离
        }
    }
    Solve ();
    for (int i = 1; i <= totq; i ++)
        printf ("%d\n", ans[i]);

    return 0;
}

/*
5 5
0 1 5
1 2 4 2
0 1 4
2 1 1 3
2 2 1 3
*/