3 岁小孩都能写的 LCT 教程

这篇博客以浅显的角度简单讲述了 LCT 的原理与一种实现方式，前置：熟练掌握任何一种树链剖分、Splay。

前言及简介

树链剖分大家都会，不就是每个点一个重儿子边，重边连起来形成一堆重链，然后查询链的信息时，可以在重链上维护一点东西（比如轻重链剖分，使用的就是线段树），一次跳完一整个重链嘛。但是，当树的形态产生变化的时候（比如在某个节点下加一个儿子什么的），线段树等静态数据结构就不能很好地维护剖分，LCT 就是用来干这事的。

不知道读者是否见过这个结论：在有根树上每次将某个点到根的轻边（作为轻儿子到父亲的边）全部改为重边（重儿子），那么一共会修改 $O((n+m)\log n)$ 次。也就是说，暴力地每次跳到所在重链的顶部，然后改掉其父亲的重儿子，然后继续往上一直到根，修改的次数是均摊 $O(\log n)$ 的。这个的证明很简单，自行思考，同时这个操作的名字叫做 access，重音是第一个音节。

实际上 LCT 就是这么暴力修改的。其次，由于你维护这个重链需要将它从中间砍开分为两个链（被新的重儿子顶替时），这里采取平衡树，准确的说是 Splay。乍一看需要 $O(m \log n)$ 次 Splay 上的操作，复杂度是均摊 $O(\log^2 n)$ 的，实际上由于 Splay 操作的特殊性，它的复杂度是均摊 $O(\log n)$ 的。别问为什么，问就是 OI 用不到。

现在你已经知道 access 是什么了，来看看如何实现吧。

Splay

前面提到了用 Splay 来维护一条重链，具体就是把这条链当做一个序列（以深度为序）。对于每条重链还需要记录其链顶的父亲是谁，这个一般记录在其 Splay 的根上。但是这样就产生一个细节：判断 $x$ 是否为根的时候，应该用 $fa_x$ 是否有儿子是 $x$。同时 rotate 的时候也要判断是否转到了根。

先来看看 Splay 的部分怎么写的：

#define get(x) (ch[fa[x]][1]==x)
#define isr(x) (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x)
void rotate(int x){
	int y=fa[x],z=fa[y],k=get(x);
	pdown(y),pdown(x);
	if(!isr(y))ch[z][get(y)]=x;
	ch[y][k]=ch[x][!k],fa[y]=x;
	if(ch[x][!k])fa[ch[x][!k]]=y;
	ch[x][!k]=y,fa[x]=z,pup(y),pup(x);
}
void upd(int x){if(!isr(x))upd(fa[x]);pdown(x);}
void splay(int x){
	upd(x);
	for(int y=fa[x];!isr(x);rotate(x),y=fa[x])if(!isr(y))rotate(get(x)==get(y)?y:x);
	pup(x);
}

为什么要维护一个翻转标记呢？看到后面就知道了，先不管。

需要一个 upd 的原因在于，平时的 Splay 都是从根往下找到当前节点，但在 LCT 中是已知了这个点，再把它旋转至根，所以一定要预先依次下传根到它的标记。

然后 rotate 里面就加了一句判根也就是 !isr(y)，Splay 就正常写，也需要判根（结束条件）。

Access

access(x) 实现了将 $x$ 到根“打通”的这个过程，具体而言每次找到 $x$ 所在重链链顶的父亲 $u$，连上 $u\to x$ 并断掉 $u$ 原来的重儿子，再从 $u$ 开始一直贯穿到根。其实现是简短而巧妙的，先看代码：

void access(int x){
	for(int y=0;x;y=x,x=fa[x])splay(x),ch[x][1]=y,pup(x);
}

每次先 splay(x)，转到当前重链的根，以获取其链顶的父亲。$y$ 保存的是，上一次跳完的是哪条重链，这样做的话 ch[x][1]=y 一句话就完成了断重和连边两个过程。最后需要更新 $x$ 的信息（因为儿子变了），并且把 $x$ 作为新的 $y$（因为对于下一条跳到的链来说，就应该连到 $x$ 所在的链上了，而 $x$ 恰好已经旋到了该 Splay 的根）。

makeroot 与 findroot

LCT 还可以支持换根和找根。

make(x) 表示把 $x$ 所在树的树根换为 $x$，具体操作是把 $x$ 到根的路打通到一个 Splay 中，然后翻转 $x$ 到根的路。注意 access 之后往往需要 splay 一下，因为打通的过程中，第一次 splay 完了我们就已经把原来的 $x$ 丢失，旋转其父亲去了，最后 $x$ 往往不是 Splay 的根。

void make(int x){access(x),splay(x),rv(x);}

然后是 find(x) 表示找到 $x$ 所在树的根是哪个。根显然是深度最浅的，把 $x$ 与根打通到一个 Splay 中然后一直往左走，找到的就是根了。注意路径上要一路下传标记，并且找到根后需要 splay 一下保证复杂度。

int find(int x){
	for(access(x),splay(x);ch[x][0];x=ch[x][0])pdown(x);
	return splay(x),x;
}

LCT 最忌滥用 findroot，因为它虽然是有返回值的函数，但它会改变 LCT 的形态。

link 与 cut

标志性的操作，不然为什么叫 LCT。

link(x,y)，连上一条 $(x, y)$ 的边。首先它们肯定属于不同连通块，你先 make(x)，再把 $x$ 挂在 $y$ 的儿子上就行了（注意，这种做法 $x$ 要作为轻儿子挂上去，否则你要 make(y) 才能作为重儿子挂上 Splay，但做麻烦了）。

void link(int x,int y){
	if(find(x)!=find(y))make(x),access(y),fa[x]=y;
}

cut(x,y)，把 $(x,y)$ 之间的边割掉。这个就比较难以处理，因为你首先要判断 $(x,y)$ 是否有边，还得知道怎么才能断开。先看看代码咋写的：

void cut(int x,int y){
	make(x);
	if(find(y)==x&&!ch[y][0]&&fa[y]==x)fa[y]=ch[x][1]=0,pup(x);
}

理解一下，先把 $x$ 作为根，然后 find(y) 一下看看是不是 $x$，也就是判连通块。

注意此时，find(y) 做了一次 access(y)，将 $y$ 到 $x$ 的路径打通了，并且把 $x$ 旋上了该 Splay 的根（因为 find(y) 找到的是 $x$ 才能进行下一步）。如果 $x\to y$ 有直接连边，那就两个充要条件：

1. $x\to y$ 在 Splay 上直接连边（$y$ 的父亲是 $x$）；
2. $y$ 的左子树为空。

思考一下这说明了什么事情：$y$ 到 $x$ 的路径上不存在比 $x$ 深且比 $y$ 浅的点。这当然可以作为判断是否有直接连边的充要条件啦。

split

没有查询叫什么数据结构？

LCT 的查询，以路径查询举例。那也就是说，只要把 $x\to y$ 的路径放进一个 Splay，它根节点的信息就是路径的信息了，这个函数我们把它叫 split(x,y)，函数名类比平衡树的分裂操作。

怎么把 $x\to y$ 的路径抽离出来？把 $x$ 作为根，然后打通 $y$ 到 $x$ 的路径不就行了嘛。

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

板题代码

查看代码

#include<bits/stdc++.h>
#define pbk push_back
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
using namespace std;
const int N=2e5+7;
int fa[N],ch[N][2],vl[N],s[N],rv[N];
#define get(x) (ch[fa[x]][1]==x)
#define isr(x) (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x)
#define rv(x) (swap(ch[x][0],ch[x][1]),rv[x]^=1)
void pup(int x){s[x]=s[ch[x][0]]^s[ch[x][1]]^vl[x];}
void pdown(int x){if(rv[x])rv(ch[x][0]),rv(ch[x][1]),rv[x]=0;}
void rotate(int x){
	int y=fa[x],z=fa[y],k=get(x);
	pdown(y),pdown(x);
	if(!isr(y))ch[z][get(y)]=x;
	ch[y][k]=ch[x][!k],fa[y]=x;
	if(ch[x][!k])fa[ch[x][!k]]=y;
	ch[x][!k]=y,fa[x]=z,pup(y),pup(x);
}
void upd(int x){if(!isr(x))upd(fa[x]);pdown(x);}
void splay(int x){
	upd(x);
	for(int y=fa[x];!isr(x);rotate(x),y=fa[x])if(!isr(y))rotate(get(x)==get(y)?y:x);
	pup(x);
}
void access(int x){
	for(int y=0;x;y=x,x=fa[x])splay(x),ch[x][1]=y,pup(x);
}
void make(int x){access(x),splay(x),rv(x);}
int find(int x){
	for(access(x),splay(x);ch[x][0];x=ch[x][0])pdown(x);
	return splay(x),x;
}
void link(int x,int y){
	if(find(x)!=find(y))make(x),access(y),fa[x]=y;
}
void split(int x,int y){make(x),access(y),splay(y);}
void cut(int x,int y){
	make(x);
	if(find(y)==x&&!ch[y][0]&&fa[y]==x)fa[y]=ch[x][1]=0,pup(x);
}
int n,m,o,x,y;
signed main(){
	scanf("%d%d",&n,&m);
	FOR(i,1,n)scanf("%d",vl+i);
	while(m--){
		scanf("%d%d%d",&o,&x,&y);
		if(!o)split(x,y),printf("%d\n",s[y]);
		if(o==1)link(x,y);
		if(o==2)cut(x,y);
		if(o==3)splay(x),vl[x]=y;
	}
	return 0;
}