好吧，这个真的很长，直接复制修改 oiwiki 的吧。

前言

Link/Cut Tree 是一种数据结构，我们用它来解决动态树问题．

Link/Cut Tree 又称 Link-Cut Tree，简称 LCT，但它不叫动态树，动态树是指一类问题．

Splay Tree 是 LCT 的基础，但是 LCT 用的 Splay Tree 和普通的 Splay 在细节处不太一样（进行了一些扩展）.

如果你不写 LCT，那你学 Splay Tree 干什么？

P3690 【模板】动态树（LCT）

P3690 【模板】动态树（LCT）。

实链剖分

对于一个点连向它所有儿子的边，我们选择一条实边剖分，这条实边跟询问有关，会根据询问动态更新。

其他边则为虚边。

对于实边，我们称它所连接的儿子为实儿子，对于一条由实边组成的链，我们同样称之为实链。

对于虚边儿子认父亲，而父亲不认儿子。

LCT

我们可以简单的把 LCT 理解成用一些 Splay 来维护动态的树链剖分，以期实现动态树上的区间操作．对于每条实链，我们建一个 Splay 来维护整个链区间的信息．

辅助树

辅助树由多棵 Splay 组成，每棵 Splay 维护原树中的一条路径，且中序遍历这棵 Splay 得到的点序列，从前到后对应原树「从上到下」的一条路径。

原树每个节点与辅助树的 Splay 节点一一对应。

由于辅助树的以上性质，我们维护任何操作都不需要维护原树，辅助树可以在任何情况下拿出一个唯一的原树，我们只需要维护辅助树即可。

对于上面的图片，是原数，下面的是辅助树，可以对着图理解一下。

原树和辅助树的关系

原树中的实链：在辅助树中节点都在一棵 Splay 中。

原树中的虚链：在辅助树中，子节点所在 Splay 的 Father 指向父节点，但是父节点的两个儿子都不指向子节点。

注意：原树的根不等于辅助树的根，原树是子树的 Splay 的中序遍历的结果。

原树的 Father 指向不等于辅助树的 Father 指向。

辅助树是可以在满足辅助树、Splay 的性质下任意换根的，虚实链变换可以轻松在辅助树上完成。

变量和函数声明

如果你要写代码，第一遍可以对着这些变量名和函数名写。

变量名

C++

ch[N][2]//左右儿子
fa[N]//父亲指向
sum[N]//路径权值和
v[N]//点权
tag[N]//翻转标记

PushUp(x)//上传
PushDown(x)//下传

函数名

Splay 和 Rotate 是基本 Splay 操作。

Access(x) 把从根到 $x$ 的所有点放在一条实链里，使根到 $x$ 成为一条实路径，并且在同一棵 Splay 里。这是最基本的必须实现的操作。

IsRoot(x) 判断 𝑥 x 是否是所在 Splay 的根。

pushall(x) 在 Access 操作之后，PushDown 所有更新信息。

MakeRoot(x) 使 $x$ 点成为原树的根。

Link(x, y) 在 $x, y$ 两点间连一条边。

Cut(x, y) 把 $x, y$ 两点间边删掉。

Find(x) 找到 $x$ 所在树的根节点编号。

Update(x, v) 修改 $x$ 的点权为 $v$ 。

Split(x, y) 提取出 $x, y$ 间的路径，方便做区间操作。

宏定义：

C++

#define ls(x) ch[x][0]//左儿子
#define rs(x) ch[x][1]//右儿子
#define isroot(x) (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x)//是否是当前 Splay 的根节点
#define dir(x) (ch[fa[x]][1]==x)//x 是它父亲的左/右节点

函数讲解

上传下传（pushup/pushdown）

这个就不用说了，线段树都写过。

C++

void pushup(int x){
	sum[x]=sum[ls(x)]^sum[rs(x)]^v[x];
}
void pushup(int x){
	if(tag[x]){
		swap(ls(x),rs(x));
		tag[ls(x)]^=1;
		tag[rs(x)]^=1;
		tag[x]=0;
	}
}

splay()/rotate()

这里 Splay() 和 Rotate() 与 Splay 树的实现有些区别。

C++

void rotate(int x){
	int y=fa[x],z=fa[y];
	if(!isroot(y))ch[z][dir(y)]=x;//注意。这里需要判断不是根节点，否则可能会连接到其他 Splay，因为这样跨过了虚边 
	int p=dir(x);
	ch[y][p]=ch[x][!p];
	fa[ch[x][!p]]=y;
	ch[x][!p]=y;
	fa[y]=x,fa[x]=z;
	pushup(y),pushup(x);//注意顺序，不然会调很久 
}
void splay(int x){
	pushall(x);
	for(int f;f=fa[x],!isroot(x);rotate(x)){
		if(!isroot(f))rotate(dir(f)==dir(x)?f:x);
	}
}

下面是 LCT 独有的函数

isroot()

我们在上面说了，虚边父亲不认儿子，但是儿子认父亲。

只需要判断这个节点是不是

C++

#define isroot(x) (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x)

Access

是 LCT的核心操作，试想我们想求解一条路径，而这条路径恰好就是我们当前的一棵 Splay。

C++

int Access(int x) {
  int p;
  for (p = 0; x; p = x, x = f[x]) {
    Splay(x), ch[x][1] = p, PushUp(x);
  }
  return p;
}

把当前节点转到根．

把儿子换成之前的节点．

更新当前点的信息．

把当前点换成当前点的父亲，继续操作．

pushall

C++

void pushall(int x){
	if(!isroot(x))pushall(fa[x]);
	pushdown(x);
}

`makeRoot()`

makeRoot() 的重要性丝毫不亚于 Access()。我们在需要维护路径信息的时候，一定会出现路径深度无法严格递增的情况，根据 AuxTree 的性质，这种路径是不能出现在一棵 Splay 中的。这时候我们需要用到 makeRoot()。

makeRoot() 的作用是使指定的点成为原树的根，考虑如何实现这种操作。设 Access(x) 的返回值为 $y$ ，则此时 $x$ 到当前根的路径恰好构成一个 Splay，且该 Splay 的根为 $y$ 。

考虑将树用有向图表示出来，给每条边定一个方向，表示从儿子到父亲的方向。容易发现换根相当于将 $x$ 到根的路径的所有边反向（请仔细思考）。因此将 $x$ 到当前根的路径翻转即可。由于 $y$ 是 $x$ 到当前根的路径所代表的 Splay 的根，因此将以 $y$ 为根的 Splay 树进行区间翻转即可。

C++

void makeRoot(int p) {
  access(p);
  splay(p);
  swap(ch[p][0], ch[p][1]);
  tag[p] ^= 1;
}

Link

Link 两个点其实很简单，先 makeRoot(x)，然后把 $x$ 的父亲指向 $y$ 即可。显然，这个操作肯定不能发生在同一棵树内，所以记得先判一下。

C++

void Link(int x, int p) {
  makeRoot(x);
  splay(x);
  fa[x] = p;
}

Split

Split 操作意义很简单，就是拿出一棵 Splay，维护的是 $x$ 到 $y$ 的路径。先 makeRoot(x)，然后 access(y)。如果要 $y$ 做根，再 splay(y)。另外 Split 这三个操作可以直接把需要的路径拿出到 $y$ 的子树上，可以进行其他操作。

C++

void split(int x,int y){
	makeroot(x);
	access(y);
	splay(y);
}

Cut

Cut 有两种情况，保证合法和不一定保证合法。如果保证合法，直接 Split(x, y)，这时候 $y$ 是根， $x$ 一定是它的儿子，双向断开即可。就像这样：

C++

void Cut(int x, int p) {
  makeRoot(x);
  access(p);
  splay(p);
  ls = fa[x] = 0;
}

如果是不保证合法，我们需要判断一下是否有，这里选择使用 map 存一下，但是这里有一个利用性质的方法：

想要删边，必须要满足如下三个条件：

$x, y$ 连通。
$x, y$ 的路径上没有其他的链。
$x$ 没有右儿子。

总结一下，上面三句话的意思就一个： $x, y$ 之间有边。具体实现就留作一个思考题给大家。判断连通需要用到后面的 find，其他两点稍作思考分析一下结构就知道该怎么判断了。

find

find() 查找的是 $x$ 所在的原树的根，请不要把原树根和辅助树根弄混。在 access(p) 后，再 splay(p)。这样根就是树里深度最小的那个，一直往左儿子走，沿途 pushDown 即可。一直走到没有 ls，非常简单。注意，每次查询之后需要把查询到的答案对应的结点 splay 上去以保证复杂度。

C++

int find(int p) {
  access(p);
  splay(p);
  pushDown(p);
  while (ls) p = ls, pushDown(p);
  splay(p);
  return p;
}

注意事项

操作前一定要想一想需不需要 pushUp 或者 pushDown，LCT 由于特别灵活的原因，少 pushdown 或者 pushup 一次就可能把修改改到不该改的点上！
LCT 的 rotate 和 Splay 的不太一样，if (z) 一定要放在前面。
LCT 的 splay 操作就是旋转到根，没有旋转到谁儿子的操作，因为不需要。

进阶应用

维护 MST

P4172 [WC2006] 水管局长

P4172 [WC2006] 水管局长。

这道题就是维护 MST 的模板，倒序做。

然后我们发现，维护 MST 可以插入一条边，然后会形成一个环，删掉环上的最长的边即可。

结合 Kruskal 可以证明，因为当前加边如果不用，那就一定在 Kruskal 过程中在这些边后加入，所以这条边不加进去了。

然后维护边权有两种思路，一是转化成点权，子节点储存边权，二是中间新建一个节点。

维护子树信息

P4219 [BJOI2014] 大融合

P4219 [BJOI2014] 大融合。

这道题中我们需要维护子树大小。

然而，LCT 只是维护实链信息的，所以我们需单独开一个数组记录虚儿子的信息。

这个用 $si$ 记录，然后我们发现我们需要在 access 时，也就是改变虚实节点的时候更新。

pushup 时也不要忘了。