简介
LCT 是常用的一种动态树。对于一般的树上问题，我们会用树剖解决，但是如果遇到动态增删边的问题就需要 LCT 来解决。
LCT 的本质上是一种链剖分，我们将所有的边剖分为虚边和实边，所以整棵树是由若干条实链构成的，实链之间用虚边相连。
我们通过 splay 来维护实链的信息，并以从上到下的顺序保持中序遍历不变，并实现各种操作。
实现
以 P3690 【模板】动态树（LCT） 为例。
基础
我们首先需要定义节点结构体：
struct Node {
int val, sum, fa, rev;//本节点的值，节点维护的子树的异或和，父节点，翻转标记
int ch[2];//两个儿子
Node () {
val = sum = fa = rev = ch[0] = ch[1] = 0;
}
} a[N];
然后我们再定义宏：
#define ls(x) a[x].ch[0]
#define rs(x) a[x].ch[1]
#define fa(x) a[x].fa
辅助函数
首先我们需要两个函数 get 和 isroot。
get 表示当前节点是父节点的左节点还是右节点，左节点返回 0，右节点返回 1。
isroot 用来判断这个节点是不是其所在实链的 splay 的根。
由于 LCT 有虚实边之分，其中实边的特点是父节点和自己互相联系，而虚边则是认父不认子，也就是说，从父结点是无法走到虚变连接的点的，但是从虚变可以走到父节点。
所以我们知道，判断一个点是不是所在实链的根，只要看其到父节点的边是不是虚边即可。只要父亲的两个儿子都不是自己就说明是虚边。
这两个函数就实现了：
bool get(int x) {//判断是那个儿子
return rs(fa(x)) == x;
}
bool isroot(int x) {//判断是不是 splay 的根，虚边认父不认子
return ls(fa(x)) != x && rs(fa(x)) != x;
}
然后我们还需要数据结构的常规操作：pushup 和 pushdown，这两个没啥好说的，这道题我们需要区间翻转（至于为什么我们之后再说），维护异或和：
void pushup(int x) {//pushup
a[x].sum = (a[ls(x)].sum ^ a[rs(x)].sum ^ a[x].val);
}
void pushdown(int x) {//pushdown
if (a[x].rev) {
swap(ls(ls(x)), rs(ls(x)));
swap(ls(rs(x)), rs(rs(x)));
a[ls(x)].rev ^= 1;
a[rs(x)].rev ^= 1;
a[x].rev = 0;
}
}
但是我们还需要一个函数 update，用来将 \(x\) 到所在实链 splay 的根的路径上所有点都 pushdown，因为我们后面的操作有些是从下往上的，所以不一定父节点就 pushdown 过了，所以需要这个函数来 pushdown。
void upd(int x) {//将 x 到 splay 根的路径都pushdown
if (!isroot(x))
upd(fa(x));
pushdown(x);
}
splay 的操作
splay 的核心操作是 rotate 和 splay。
rotate 与正常的 splay 基本一样，但是有一点要注意：正常我们需要找到 \(x\) 的父节点 \(y\) 和爷爷 \(z\)，如果爷爷存在，就要更新爷爷的儿子。但是由于现在是在 LCT 中，我们需要用 isroot 来判断爷爷存不存在，而不能简单地用是不是 0 来判断。
void rotate(int x) {
int y = fa(x), z = fa(y), k = get(x);//x - y - z, k 表示 x 是哪边的
if (!isroot(y))//如果 y 不是根，就把 z 的 y 儿子变成 x
a[z].ch[get(y)] = x;
fa(a[x].ch[1 - k]) = y;//将 x 的儿子过继给 y
a[y].ch[k] = a[x].ch[1 - k];
a[x].ch[1 - k] = y;//将父节点变成自己的子节点
fa(y) = x, fa(x) = z;//更新父节点指向
pushup(y), pushup(x);//注意顺序!!!
}
而 splay 也类似，需要将判断是不是根用 isroot 来判断，这一条适用于所有操作。
我的写法遵循的逻辑是：如果需要旋父亲就旋父亲，否则一直旋自己。而不是一次性两次旋自己，但是或以下图就会发现这启示是等价的，没用影响。
注意最开始要 update 一下。
void splay(int x) {//将 x 变成根
upd(x);//更新整个路径
while (!isroot(x)) {//只要不是根
if (!isroot(fa(x)) && !isroot(fa(fa(x))) && get(x) == get(fa(x)))
rotate(fa(x));//如果都是同一边都一样就转父亲
//上面需要判断父亲和爷爷是不是根，否则都不能双旋
rotate(x);//自己肯定会转
}
}
access
LCT 的核心操作之一，将 \(x\) 到原树的根的路径上的所有边都变成实边。
我们考虑该如何实现，对于一个点，首先我们将 splay 到根，然后我们需要跨过虚边的限制。
现在我们的父节点并不认识我们，所以我们需要尝试将我们挂到这个父节点下面，成为实边。
所以我们将父节点 splay 到根，由于我们是按照中序遍历，所以我们需要变成其右儿子。
但是如果人家本来有右儿子怎么办？考虑到虚边认父不忍子，我们直接修改，这样那个右儿子就变成了虚边！！！！
所以我们这样就可以将到根路径上所有边变成实边。
我们可以更进一步，如果最开始我们把 \(x\) 的右儿子也变成虚边，那么最终得到的链将会只包括根到 \(x\) 的路径上的点。
于是我们就实现了这个功能。代码中我们通过储存上一个点来实现：
void access(int x) {//将 x 到根的路径变成实链，并且没有其他点
int p = 0;//上次的点
while (x) {//只要 x 还有
splay(x);//把 x 旋到根
rs(x) = p;//这一步首先踢掉了原来的儿子，变成了新的儿子
pushup(x);//更新一下
p = x, x = fa(x);//更新
}
}
makeroot
makeroot 也是核心操作之一，我们现在想要将 \(x\) 变成原树的根（换根）。
首先，我们先 access 变成实链，由于不知道 splay 根节点，我们可以 splay(x) 变成根。
现在我们需要用到翻转标记了，我们发现换根之后有且只有这条链上的顺序会发生翻转，于是我们打一个翻转标记即可（不要忘了同时也要交换左右儿子）。
void makeroot(int x) {//将 x 变成原树的根
access(x);//弄到同一颗 splay 上
splay(x);//将 x 变成根
//现在由于没有其他点，所以我们可以直接反转整个链
a[x].rev ^= 1;//翻转标记
swap(ls(x), rs(x));//翻转
}
findroot
findroot 用来找到 \(x\) 所在原树的根。
我们依然是 access 加 splay，然后我们发现根应该是第一个，所以我们不断地找左儿子即可。
注意找的同时需要 pushdown，并且为了保证时间复杂度最后需要 splay 一下。
int findroot(int x) {//查找所在原树的根
access(x);
splay(x);
while (ls(x)) {//只要还有左儿子
pushdown(x);//先pushdown
x = ls(x);
}
splay(x);//保证复杂度
return x;
}
split
将 \(x\) 到 \(y\) 的路径上单独变成一棵 splay。
这个很简单，直接 makeroot + access + splay 即可，最后在 y 上处理。
void spt(int x, int y) {//将 x 到 y 单独拿出来作为一棵 splay, 并且 y 是根
makeroot(x);
access(y);
splay(y);
}
link cut
两个核心操作，连接与切除。
对于链接来说，我们先 makeroot(x)，然后如果本来不在于一起，那么就把 x 变成 y 的虚儿子。
对于切除，依然是先 makeroot(x)，然后我们思考条件：x 和 y 联通且路径上没有别的点，也就是 y 是 x 的右儿子且没有左儿子。
这种写法将本来需要的 access 和 splay 操作在 findroot 里就有了，所以 if 的顺序不能变！
void link(int x, int y) {//加一条边在 x 和 y 之间
makeroot(x);//将 x 变成树的根
if (findroot(y) != x)//如果 y 和 x 不在一起
fa(x) = y; //这里是虚儿子
pushup(x);//更新 x
}
void cut(int x, int y) {//x 和 y 的边切断
makeroot(x);
//顺序不能变！findroot蕴含了access和splay x 到根的操作
if (findroot(y) == x && fa(y) == x && !ls(y))
fa(y) = rs(x) = 0;//双向断开
pushup(x);//更新 x
}
完整代码
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
namespace LCT {
struct Node {
int val, sum, fa, rev;//本节点的值，节点维护的子树的异或和，父节点，翻转标记
int ch[2];//两个儿子
Node () {
val = sum = fa = rev = ch[0] = ch[1] = 0;
}
} a[N];
#define ls(x) a[x].ch[0]
#define rs(x) a[x].ch[1]
#define fa(x) a[x].fa
bool get(int x) {//判断是那个儿子
return rs(fa(x)) == x;
}
bool isroot(int x) {//判断是不是 splay 的根，虚边认父不认子
return ls(fa(x)) != x && rs(fa(x)) != x;
}
void pushup(int x) {//pushup
a[x].sum = (a[ls(x)].sum ^ a[rs(x)].sum ^ a[x].val);
}
void pushdown(int x) {//pushdown
if (a[x].rev) {
swap(ls(ls(x)), rs(ls(x)));
swap(ls(rs(x)), rs(rs(x)));
a[ls(x)].rev ^= 1;
a[rs(x)].rev ^= 1;
a[x].rev = 0;
}
}
void upd(int x) {//将 x 到 splay 根的路径都pushdown
if (!isroot(x))
upd(fa(x));
pushdown(x);
}
void rotate(int x) {
int y = fa(x), z = fa(y), k = get(x);//x - y - z, k 表示 x 是哪边的
if (!isroot(y))//如果 y 不是根，就把 z 的 y 儿子变成 x
a[z].ch[get(y)] = x;
fa(a[x].ch[1 - k]) = y;//将 x 的儿子过继给 y
a[y].ch[k] = a[x].ch[1 - k];
a[x].ch[1 - k] = y;//将父节点变成自己的子节点
fa(y) = x, fa(x) = z;//更新父节点指向
pushup(y), pushup(x);//注意顺序!!!
}
void splay(int x) {//将 x 变成根
upd(x);//更新整个路径
while (!isroot(x)) {//只要不是根
if (!isroot(fa(x)) && !isroot(fa(fa(x))) && get(x) == get(fa(x)))
rotate(fa(x));//如果都是同一边都一样就转父亲
//上面需要判断父亲和爷爷是不是根，否则都不能双旋
rotate(x);//自己肯定会转
}
}
void access(int x) {//将 x 到根的路径变成实链，并且没有其他点
int p = 0;//上次的点
while (x) {//只要 x 还有
splay(x);//把 x 旋到根
rs(x) = p;//这一步首先踢掉了原来的儿子，变成了新的儿子
pushup(x);//更新一下
p = x, x = fa(x);//更新
}
}
void makeroot(int x) {//将 x 变成原树的根
access(x);//弄到同一颗 splay 上
splay(x);//将 x 变成根
//现在由于没有其他点，所以我们可以直接反转整个链
a[x].rev ^= 1;//翻转标记
swap(ls(x), rs(x));//翻转
}
int findroot(int x) {//查找所在原树的根
access(x);
splay(x);
while (ls(x)) {//只要还有左儿子
pushdown(x);//先pushdown
x = ls(x);
}
splay(x);//保证复杂度
return x;
}
void spt(int x, int y) {//将 x 到 y 单独拿出来作为一棵 splay, 并且 y 是根
makeroot(x);
access(y);
splay(y);
}
void link(int x, int y) {//加一条边在 x 和 y 之间
makeroot(x);//将 x 变成树的根
if (findroot(y) != x)//如果 y 和 x 不在一起
fa(x) = y; //这里是虚儿子
pushup(x);//更新 x
}
void cut(int x, int y) {//x 和 y 的边切断
makeroot(x);
//顺序不能变！findroot蕴含了access和splay x 到根的操作
if (findroot(y) == x && fa(y) == x && !ls(y))
fa(y) = rs(x) = 0;//双向断开
pushup(x);//更新 x
}
}
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> LCT::a[i].val, LCT::a[i].sum = LCT::a[i].val;
for (int i = 1, op, x, y; i <= m; i++) {
cin >> op >> x >> y;
if (op == 0) {
LCT::spt(x, y);
printf("%d\n", LCT::a[y].sum);
}
else if (op == 1)
LCT::link(x, y);
else if (op == 2)
LCT::cut(x, y);
else {
LCT::makeroot(x);
LCT::splay(x);
LCT::a[x].val = y;
LCT::pushup(x);
}
}
return 0;
}