初中生都能看懂的 LCT 学习笔记

这篇文章偏向入门，旨在尽可能解决一类问题——动态树，主要讲述并且整理 LCT 算法及其一些变式。

目前其变式例题作者还在整理之中，编者保证会把变式例题持续更新。

0.前置知识

splay。

我可以猜测一下，你们可能看到 splay，然后就可能去学了 splay 树，然后接着可能因为要写模板题，于是就去写 P3369 了。

~~然后回来仰天长啸，素质有待提高的同学就会把怒火撒在笔者身上~~：splay 这种东西，我一个 P3369 的代码的 splay 树部分就要写 $1.9k$，这也太难调试了。这要上 LCT 不得难得逆天？~~笔者，你过来，我保证不打死你！~~

前面 P3369 的题目的各种操作，即使是插入和删除，就需要很多比较复杂的处理；查询第 $k$ 小也是多少有点麻烦，还有一箩筐前驱后继之类的操作，确实不很简洁。

实际上，在解决普通平衡树这类问题里面，splay 算法完全没有压倒性的优势。不用说权值线段树可以更加简洁地实现，FHQ-Treap 也可以在二十行代码内优雅地解决这道题目，更不必说常数更加优秀的 __gnu_pbds::tree 了，在它们之前，splay 的三四十行代码就显得相形见拙。

但是，我们处理的是 动态树 问题。这可和我们普通的平衡树不一样啊。

好消息是，在此之中，我们只需要维护一个操作—— splay(p) ！

可能我们还需要支持单点修改之类的操作，这类操作不算困难，至少比普通平衡树的操作简单多了是吧（摊手）。

而 LCT 里面的 splay 树结构，需要做一些小小的改动，来支持 LCT 的特性。

树链剖分。

我们应该见过应用树链剖分算法的题目，题型和解决方法如下：

有一棵静态树，修改/查询某两点之间路径上所有点的点权（或者是边权）之和，或者最大值、最大子段和这类的答案。

解决此类题目，通常的解法是直接对原树进行轻重链剖分。

然后我们将 $x$ 到 $y$ 的 $lca$ 求出来。在求解 $lca$ 的过程之中，顺便对 $x$ 到 ${lca}$ 和 $y$ 到 $lca$ 的路径操作。

把 $x$ 和 $y$ 跳到它们的 $lca$，并且贡献答案的这个过程，是一个自底向上、从一条重链的顶端，通过一条轻边跳到另一条重链里面的过程。

而通过预处理，可以得到一段重链的 $dfs$ 序是连续的，所以我们可以使用区间数据结构来解决这样的问题。

而一条 $x$ 到 $y$ 的路径至多被拆成 $O(\log_2 n)$ 条链（经过的轻边条数），所以时间复杂度能够做到 $O(t\log n)$，其中 $t$ 为这个区间数据结构处理连续区间的数据的单次时间复杂度。

有的同学会坐不住了：你扯那么多没用的数据结构干什么啊？

别急。因为我们 LCT 的一些操作也是从“重链顶”通过一条“轻边”跳到另一条“重链”里面。

1.算法本质

LCT,全称 Link-Cut Tree。即是可以支持断边、加边的一种数据结构。

巧妇难为无米之炊，没有要维护的东西只是空谈而已。

所以我们先需要明确 LCT 维护的是什么，支持什么操作，然后再代码实现。

首先 LCT 它维护的是原图中的森林，它的结构也是森林。这个很好理解，因为题目所能维护的也不一定是一棵树。

然后，它支持加边，删边，这点是必要的。不然还叫什么 LCT。

LCT 建立的森林之中的每棵树（我们称为“辅助树”）的结构和原树的关系不是那么的紧密，但是有一些性质是相同的。

接着，我们的 LCT 的核心是什么？

具体而言，LCT 对了每棵树进行了虚实链剖分，通过 splay 维护每一条实链上面的所有节点（按照深度由浅至深的顺序），通过 splay 灵活易变的结构特性，来达成虚实链变化的目的，从而支持更多操作。

虚实链是什么鬼？怎么个维护法？我的 splay 又应该按照什么顺序去维护实链？怎么虚实链变化？

别急，一个个来。

对于 LCT 上的每个节点，它都是属于某一条实链之中的。

类比：前面提到了轻重链剖分，每个节点也是属于某一条重链之中的。

实链是一条树中的链。一棵有根树的内部节点（就是非叶子节点啦）有且仅有一条实边指向它的某个儿子。

和轻重链剖分不同的是，这里的儿子没有强制钦定是子树大小最大的那个，也不是像长链剖分那样钦定是子树出链最长的那一个。

它是随便一个儿子，这个儿子没有特殊性质，就是单纯被程序选中了而已。

那么我们就能够使用一种数据结构维护这一些实链了。

因为实链的建立不依赖儿子的特殊性质，所以我们可以建出不同形态的 LCT 了。

同时，也让某条虚边变化为实边、实边变化为虚边的操作，成为了可能。

而这里维护实链的数据结构，也需要和虚实边的变换契合，如果一条实边变成了虚边，这个数据结构就要拦腰砍断；如果一条虚边变成了实边，这个数据结构需要移花接木（比喻不太恰当，大家凑合着看吧），总之就是要有灵活的特性。

喂喂喂，扯这些东西有啥用？我要解决问题，不是听你普及嫁接技术的！快点快点！

2.算法特性

这个算法能够维护动态加边、删边同时又能保证维护实链集合的法宝，在于几个操作。

首先，它支持把一个指定点到根的路径上的所有边，全部变成实边。换句话说，让它们全都出现在一条实链里面。

这个操作叫做 access(x)。

其次，它支持把根设为一个任意节点 $x$。

这个操作叫做 makeroot(x)。

实际上还有一个操作，把任意节点 $x$ 设为它所属的实链的“领导节点”。

这个操作叫做……我知道，我知道，你们别抢答，就假设它是 leader(x) 吧。

这里“领导节点”是什么，不需要管它，希望你们耐着性子接着看下去。

所以 makeroot(x) 这个操作等价于：

先执行 access(x) 操作。
再执行 leader(x) 操作。

如果我知道了 access(x) 和 leader(x) 怎么实现，那么如何维护形如以下操作呢？（假设以下操作均合法）

path(x,y)：求得 $x$ 到 $y$ 的路径的某些权值，比如异或和。
cut(x,y)：将从 $x$ 到 $y$ 的边断开。
link(x,y)：加入一条 $x$ 到 $y$ 的边。

先来看第一个操作。

一个可以支持区间分离的数据结构多少有点复杂了吧！

于是考虑把 $x$ 到 $y$ 的路径，通过上面两个 LCT 的基本操作分离出来。

假设我已经把 $x$ 到根的路径搞出来了，那么就不妨让 $x$ 当作“根”，然后再求得 $y$ 到“根”的路径。

求出这个路径，应该就是答案了，把这条路径用某种数据结构算出来，也许就是答案？？？

不要剧透，不要剧透，要保证节目效果。

假设答案是对的。假设这条实链上没有别的点，刚好就是 $x$ 到 $y$ 路径上面的所有点。

那这个流程就是：

makeroot(x)
access(y)
leader(y)
求得 $x$ 到 $y$ 的所有贡献。（在一条实链上，就好处理了）

那么 cut(x,y) 的操作也能做了呀！

把 $x$ 到 $y$ 的实链搞出来，这个时候实链应该只有两个点，其中 $y$ 是领导节点。

那么我们把 $x$ 和 $y$ 相连的那条边断掉就行啦！

类似的，link(x,y) 操作，但是它们不在一棵树之内。

那么我们只需要把 $x$ 变为“领导节点”，然后对于 $x$ 向 $y$ 连一条虚边，就行啦！

“这个博主是不是傻逼，扯那么多没用的东西，什么“领导节点”一点都不懂，一点代码都不给，也不讲 splay 在这棵树的运用，点踩+举报了”

“你说得对，而且博主自己都没有证实 path(x,y) 方法的正确性”

喂喂喂你们别走啊！我还没讲完啊！QAQ

3.splay 操作

上面那些东西空讲，确实确实很抽象，因为我压根不知道哪里有这样一个数据结构维护这样一些东西。

然而前面提到的 splay 都等了很久了，怎么还没上场？

这就上。

首先 splay 就是维护实链的工具，而一条实链的“领导节点”就是当前实链对应的 splay 的根。

而 access 操作就是让 $x$ 到根的路上遇到的所有节点都在一个 splay 里面。

要不要把 $x$ 下面的节点放进去呢？代码实现上，是不需要的。（毕竟把儿子放进去就很麻烦了）

所以上面的 path(x,y) 方法就是正确的。

这里的 leader(x) 实际上就是 splay(x)。

以后我们抛弃“领导节点”这个称谓了，直接用实链的根代替。

稍微讲一下这里 LCT splay 和正常 splay 的区别。

LCT 有很多很多实链和虚边。

而我们知道实链的上面肯定有一条虚边指上去（根除外）。

那么也就是每条实链的根其实是有父亲节点的（原树的根除外）。

但是一个父亲节点能够挂多个儿子啊？？！那么怎么存储呢？

我们发现这个父亲节点和它的虚边儿子（们）不能说毫无关联，只能说关系不那么紧密。splay 的时候，不能够以它为父亲节点再跑上去。

（当然有一些题目会用到这种关系的，比如求一个动态连通块大小）

那就这样：儿子认父亲，但是父亲不认儿子。

这样的方法也是方便我们之后做 access 操作。

然后 splay 操作的时候要判断一个节点为根。这个时候就判断它的爹认不认它就行了。

4.代码实现

接下来终于讲代码了。

首先放一个模板：（功能不全，请大佬轻喷）

class lct{
private:
	I u[N][2],fa[N],rvt[N];
	#define ls u[x][0]
	#define rs u[x][1]
	V rev(I x){if(x)rvt[x]^=1,swap(ls,rs);}
	V psd(I x){if(x&&rvt[x])rev(ls),rev(rs),rvt[x]=0;}
	bool of(I x){return u[fa[x]][1]==x;}
	bool nrot(I x){return u[fa[x]][0]==x||of(x);}
	V dwt(I x){if(nrot(x))dwt(fa[x]);psd(x);}
	V rot(I x){I y=fa[x],z=fa[y],ofx=of(x);
		if(nrot(y))u[z][of(y)]=x;
		u[y][ofx]=u[x][ofx^1];fa[u[x][ofx^1]]=y;
		u[x][ofx^1]=y;fa[y]=x;fa[x]=z;}
	V splay(I x){dwt(x);
		for(I fx;fx=fa[x],nrot(x);rot(x))
			if(nrot(fx))rot(of(x)==of(fx)?fx:x);}
	V access(I x){
		for(I p=0;x;p=x,x=fa[x])
			splay(x),rs=p;}
public:
	V mroot(I x){
		access(x);splay(x);rev(x);}
	I froot(I x){
		access(x);splay(x);
		for(;ls;x=ls);
		return splay(x),x;} 
	V link(I x,I y){
		mroot(x);fa[x]=y;}
	V cut(I x,I y){
		mroot(x);
		if(x!=froot(y)||u[y][0]||fa[y]!=x)return;
		fa[y]=rs=0;}
	V path(I x,I y){mroot(x);access(y);splay(y);}
	bool can(I x,I y){return froot(x)==froot(y);}
}T;

接下来一行行解释这是啥。

首先我用了个 class 封装，功能类似 struct，不细讲，你不习惯就换成 struct 得了，记得把 private 和 public 删掉。

（经典笑话：）

These are my private!
Yes,but we are in the same class!

首先看变量和宏定义这几行。其中 I 代表 int 类型。

I u[N][2],fa[N],rvt[N];
#define ls u[x][0]
#define rs u[x][1]

u 数组代表节点的左右儿子是啥，fa 数组表示爹是啥（重复一遍：爹不一定认崽，不认就说明是虚的）

rvt 代表翻转标记，这点之后会讲到，它的作用是打上翻转左右儿子的标记。

这两个 ls 和 rs 的宏定义算是简写，代表 x 的左右子树。

实际问题上面我们可能还要维护 siz 数组之类的东西或者整棵树的和，总之就是你想维护啥就维护啥。

然后看这几个函数。其中的 V 我已经 typedef 成 void，即代表 void 类型。

V rev(I x){if(x)rvt[x]^=1,swap(ls,rs);}
V psd(I x){if(x&&rvt[x])rev(ls),rev(rs),rvt[x]=0;}
bool of(I x){return u[fa[x]][1]==x;}
bool nrot(I x){return u[fa[x]][0]==x||of(x);}
V dwt(I x){if(nrot(x))dwt(fa[x]);psd(x);}

第一行，翻转 x，顺便标记。这个功能显然，但是需要注意 x 存在不存在。

第二行，下传标记。就是翻转左右节点并且清空标记就可以了。

第三行，of(x) 函数代表 x 是它父亲的第几个子树。返回 $0$ 就说明它在左边，反之在右边。

第四行，nrot(x) 代表 x 是不是根，就是判断它的爹认不认崽。

第五行，dwt(x) 是个递归函数，是要从当前所在的 splay 的根一直下传标记到 x 的。

你别看他短，但是它是非常重要的，因为不从根下传标记一路下来的话，会删掉不该删的子树，添加不该加的子树，导致整棵 LCT 形态错误。

现实生活之中，还需要有个 psu(x) 维护 x 子树的信息。

然后要入门一些 splay 系函数了。

V rot(I x){I y=fa[x],z=fa[y],ofx=of(x);
	if(nrot(y))u[z][of(y)]=x;//这里变动了
	u[y][ofx]=u[x][ofx^1];fa[u[x][ofx^1]]=y;
	u[x][ofx^1]=y;fa[y]=x;fa[x]=z;
    //这里还需要一行 psu(y);psu(x); 先更新 y 再更新 x，代码没有实现
}
V splay(I x){dwt(x);
	for(I fx;fx=fa[x],nrot(x);rot(x))
		if(nrot(fx))rot(of(x)==of(fx)?fx:x);}

首先 rot 函数，别的东西都没啥变动，但是 if(nrot(y))u[z][of(y)]=x; 这行代码却判断了一下 y 是否为当前实链的根。

为什么？因为要保证虚边中爹不认崽的性质。如果 $y$ 为根，那么 $y$ 连接它父亲的一定是条虚边。

然后别的操作照旧。就这么简单。

其次 splay 函数，在 x 访问时候，要递归下传标记（只有这一处地方要下传）。

然后别的操作照旧。这里判根是上述 nrot 函数。

有的同学可能不会 splay，这里简单科普一下。

首先旋转操作 rot(x) 就是把一个 x 旋到它父亲的位置，让父亲变为它的某个儿子。这部分涉及到少量边的修改。

然后 splay 操作就是把 x 旋转到所在平衡树的根（这里是旋转到所在实链的根）。

这里使用了双旋操作。

具体而言，如果 $x$ 和父节点 $fa$ 都是同向（比如 $x$ 是 $fa$ 的左儿子，而且 $fa$ 也是某个节点的左儿子）那就先旋转 $fa$；

否则旋转 $x$；最后还要把 $x$ 往上面旋转一层，做到一次旋转两层的目的。

所以代码写起来就是这个样子。

话题聊回来，LCT 还差一个最核心的操作：access。

V access(I x){
	for(I p=0;x;p=x,x=fa[x])
		splay(x),rs=p;}

这个操作的流程是自底向上把 $x$ 到根的路径提取出来。

这个 p 实则为当前实链的下一条实链的根（是深度的下方）。

然后我们把 $x$ 旋转到所在实链的根，此时 $x$ 的左子树是深度小于它的，这一部分反而不需要动；

反而 $x$ 的右子树是深度大于它的。但是这个时候我们记录了下一条实链的根 $p$。

记住：access(x) 这个操作是自底向上把 $x$ 到根的路径提取出来，让这条路径出现在一条实链里面。

所以理所应当的，我们抛弃了当前 $x$ 的右子树，改为 $p$。

再次强调虚边是爹不认崽，但是崽认爹。

所以当前 $x$ 那个被抛弃的右子树还是认 $x$ 当爹。（实际上基于虚边的性质可以做连通块大小之类的操作）

这个时候本来 $p$ 到 $x$ 是虚边来着，现在很好，这个爹 $x$ 认它当崽了，它理所应当就成为了实边。

更新右子树之后还需要更新 $x$ 的答案。这里没写 psu(x)。

简单吧？简洁吧？

*嘘声一篇*

没事，前面确实很难，代码也确实简短但是不好理解。前面的各个细节都不能错。

但是，接下来 public 里面的就很简单了。

这里放全部代码：

public:
	V mroot(I x){
		access(x);splay(x);rev(x);}
	I froot(I x){
		access(x);splay(x);
		for(;ls;x=ls);
		return splay(x),x;} 
	V link(I x,I y){
		mroot(x);fa[x]=y;}
	V cut(I x,I y){
		mroot(x);
		if(x!=froot(y)||u[y][0]||fa[y]!=x)return;
		fa[y]=rs=0;}
	V path(I x,I y){mroot(x);access(y);splay(y);}
	bool can(I x,I y){return froot(x)==froot(y);}
}T;

首先 mroot(x) 是 makeroot(x) 的简写，代表让 x 变成根。

这个操作首先提取实链，然后让 x 变成实链的根。

但是这还是不够。我们要让 $x$ 当上原树的根。

观察，$x$ 是这条实链的最末端，而且它是所在实链的根。

换句话说，它没有右子树，如果让 $x$ 当根的话，那么就要翻转整条实链。

不知道大家有没有做过文艺平衡树那题，于是打个标记就完了。

这也就是为什么前面一直强调标记下传，但是为什么又没见到打标记的操作的原因。

然后 froot(x) 是 findroot(x) 的简写，代表 $x$ 所在树的根。

类似的，先 access 再 splay，这样只需要找最左边的子树，就是这条实链深度最小的节点，即为根。

记得把这个根 splay 上去！

接着 link(x,y) 操作，我们让 $x$ 为他所在连通块的根，然后连一条到 $y$ 的虚边即可。

如果不合法用 froot(x)==froot(y) 判断一下即可。