用下图表示一颗 Splay，其中从左到右为中序遍历，角标代表根，虚线箭头代表根的父亲（如果虚线箭头指向自己代表指向 00）。

比如下面这颗由两颗 Splay 组成的辅助树：

该辅助树用点线法表示就是：

该辅助树对应的原树是：

下面来图解 Lct 的这几种基本操作。

  1. splay(x)\text{splay}(x)

    splay 操作是 splay 到当前 Splay 的根。

    这颗 splay 底下的几条指向它的虚边代表可能有若干个 splay 指向该 splay 的节点，当然也可能没有。

  2. access(x)\text{access}(x)

    access 操作的具体图示，上边为辅助树的变化图示，下边为原树的变化图示：

  3. makeroot(x)\text{makeroot}(x)

  4. findroot(x)\text{findroot}(x)

  5. Split(x,y)\text{Split}(x,y)

注意事项：

  1. 对点 x 调用函数 splay 之前，必须要保证 x 到当前 splay 的根的路径上没有懒标记了。也就是说，可以调用函数 splay(x) 当且仅当：

    1. 点 x 是从当前 splay 的根递归地找下来的，在向下递归的过程中调用了函数 pushdown。

    2. 上一步调用了 update(x)。

  2. 函数 rotate 和 splay 中判断父亲存不存在的方法应为 if (isroot(fa[x]) == 0)（点 x 换成其他点同理）。

Luogu P3690 【模板】动态树（Link Cut Tree）

代码：

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
#include<bits/stdc++.h>
using namespace std;
const int MAXn = 1e5;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

int ndval[MAXn + 10];

int son[MAXn + 10][2], fa[MAXn + 10];
int xorr[MAXn + 10];
int lzrev[MAXn + 10];
inline void putrev(int id) {
    swap(son[id][0], son[id][1]);
    lzrev[id] ^= 1;
}
inline void pushdown(int id) {
    if (lzrev[id]) {
        if (son[id][0]) putrev(son[id][0]);
        if (son[id][1]) putrev(son[id][1]);
        lzrev[id] = 0;
    }
}
inline void pushup(int id) {
    xorr[id] = ndval[id] ^ xorr[son[id][0]] ^ xorr[son[id][1]];
}
inline int isroot(int id) {
    return son[fa[id]][0] != id && son[fa[id]][1] != id;
}
inline int side(int id) {
    return son[fa[id]][1] == id;
}
inline void rotate(int id) {
    int y = fa[id], z = fa[y], sideid = side(id), s = son[id][sideid ^ 1];
    if (isroot(y) == 0) {son[z][side(y)] = id;} fa[id] = z;
    son[id][sideid ^ 1] = y; fa[y] = id;
    son[y][sideid] = s; if (s) {fa[s] = y;}
    pushup(y); pushup(id);
}
void splay(int id) {
    int y;
    while (isroot(id) == 0) {
        y = fa[id];
        if (isroot(y) == 0) {
            if (side(id) == side(y)) rotate(y);
            else rotate(id);
        }
        rotate(id);
    }
}
int cntpa, pa[MAXn + 10];
void update(int id) {
    cntpa = 0;
    while (true) {
        pa[++cntpa] = id;
        if (isroot(id)) break;
        id = fa[id];
    }
    for (int i = cntpa; i; --i) {
        pushdown(pa[i]);
    }
}
void access(int x) {
    int backupx = x;
    for (int s = 0; x; s = x, x = fa[x]) {
        update(x);
        splay(x);
        son[x][1] = s;
        pushup(x);
    }
    update(backupx);
    splay(backupx);
}
void makeroot(int x) {
    access(x);
    putrev(x);
}
int findroot(int x) {
    access(x);
    int rt = x;
    while (true) {
        pushdown(rt);
        if (son[rt][0] == 0) break;
        rt = son[rt][0];
    }
    splay(rt);
    return rt;
}
void split(int x, int y) {
    makeroot(x);
    access(y);
}
void link(int x, int y) {
    makeroot(x);
    if (findroot(y) != x) fa[x] = y;
}
void cut(int x, int y) {
    makeroot(x);
    if (findroot(y) == x && fa[y] == x && son[y][0] == 0) {
        son[x][1] = fa[y] = 0;
        pushup(x);
    }
}

int n, m;
signed main() {
    read(n, m);
    for (int i = 1; i <= n; ++i) {
        read(ndval[i]);
        pushup(i);
    }
    for (int i = 1, opt, x, y; i <= m; ++i) {
        read(opt, x, y);
        if (opt == 0) {
            split(x, y);
            printf("%d\n", xorr[y]);
        } else if (opt == 1) {
            link(x, y);
        } else if (opt == 2) {
            cut(x, y);
        } else {
            update(x);
            splay(x);
            ndval[x] = y;
            pushup(x);
        }
    }
    return 0;
}

其中 putrev 和 pushdown 这两个函数有两个版本，先 swap 版（就是上面代码用的的版本）：

1
2
3
4
5
6
7
8
9
10
inline void putrev(int id) {
    swap(son[id][0], son[id][1]);
    lzrev[id] ^= 1;
}
inline void pushdown(int id) {
    if (lzrev[id]) {
        putrev(son[id][0]); putrev(son[id][1]);
        lzrev[id] = 0;
    }
}

后 swap 版：

1
2
3
4
5
6
7
8
9
10
inline void putrev(int id) {
    lzrev[id] ^= 1;
}
inline void pushdown(int id) {
    if (lzrev[id]) {
        swap(son[id][0], son[id][1]);
        putrev(son[id][0]), putrev(son[id][1]);
        lzrev[id] = 0;
    }
}

如果使用第二个版本，那么需要保证在 splay 中从上往下操作时所有对儿子节点的操作和询问都应该在 pushdown 之后进行。