[数据结构与算法]模板：Link Cut Tree

所谓Link Cut Tree，就是林可卡特发明的tree

（逃）

前言

终于走到了这一天…
其实感觉没有预想的那么难（单纯就学习算法和理解模板而言）
至少感觉比学平衡树轻松

LCT是一种很强大的树形数据结构
最重要的功能优势就是支持双log的复杂度完成加边、删边、换根的操作
在路径问题上十分强大

解析

原理

LCT的核心原理是实链剖分
和重链剖分类似的，将一棵树中的边分为实边和虚边
每个结点的最多有一条连向儿子的实边（与树链剖分不同的，也可以没有）

把实边连成的链成为实链
把在同一条实链上的结点放到同一个splay中
这个splay的中序遍历就是这条链从上到下的顺序
这样就间接的表示了所有实边的信息

那么如何表示虚边？
假设原树上有一条 $fa$ 指向$son$的虚边
就把son所在的splay的根节点指向fa，从而表示出虚边
根节点也有父亲了，如何判断根节点呢？
只有该结点的父亲的左右儿子都不是自己，那么这个结点就是根节点

inline bool isroot(int x) {
	return tr[f[x]][0]!=x&&tr[f[x]][1]!=x;
}

下面我们来讲讲具体的操作函数

rotate(x)

和普通的splay大同小异，唯一需要注意的是有一句

if(gfa) tr[gfa][which(fa)]=x;

变成了：

if(!isroot(fa)) tr[gfa][which(fa)]=x;

较好理解，因为判定根的条件变了

splay(x)

将x转到所在splay的根节点，由于只需要转到根一个功能，穿一个参即可
注意：不同于正常的splay，需要先把链上的标记下放
实现有两种方法
第一种是递归：

void pushall(int x){//printf("%d\n",x);
	if(!isroot(x)) pushall(f[x]);
	pushdown(x);
}

第二种是手写栈：

int y=x,top=0;
	zhan[++top]=y;
	while(!isroot(y)) zhan[++top]=y=f[y];

建议使用第二种，因为第一种不小心容易写完函数后忘记调用（别问我为什么知道）
然后和rotate类似的，对根的判断略有区别
不过都是一个道理

inline void splay(int x) {
	int y=x,top=0;
	zhan[++top]=y;
	while(!isroot(y)) zhan[++top]=y=f[y];
	while(top) pushdown(zhan[top--]);
	for(int fa; fa=f[x],!isroot(x); rotate(x)) {
		if(!isroot(fa)) which(fa)==which(x)?rotate(fa):rotate(x);
	}
	return;
}

access(x)

重中之重，LCT的灵魂

功能：提取出 x 到根节点的一条实链

先把x的尾巴去掉，具体来说就是转到根，然后砍掉右子树
然后一路往上直至 fa 指针为空，过程中需要改变实虚边的状态

inline void access(int x) {
	for(int y(0); x; y=x,x=f[x]) {
		splay(x);tr[x][1]=y;pushup(x);
		if(y) f[y]=x;
	}
	return;
}

findroot(x)

功能：找到x所在的树的根节点（注意是真实的树而不是splay的根）

先access(x)，然后把x转到根，不断往左走即可

inline int findroot(int x) {
	access(x);splay(x);
	while(pushdown(x),tr[x][0]) x=tr[x][0];
	splay(x);
	return x;
}

makeroot(x)

功能：把x作为其所在树的根（换根）
前面说过，父子关系在splay中的体现是中序遍历
所以换根（即颠倒x-rt路径上所有的父子关系），其实就是区间翻转
先access(x)，然后转到根，然后用类似文艺平衡树的方式在x上打一个翻转标记即可

inline void makeroot(int x) {
	access(x);splay(x);tag(x);
	return;
}

（最愉快的代码）

split(x,y)

功能：提取出以x、y为两端点的实链（前提是二者联通）

makeroot(x)之后access(y)即可
为了后面方便，常常再加一步splay(y)（不然连根是谁都不知道提取个寂寞）

inline void split(int x,int y){//y is father
	makeroot(x);access(y);splay(y);
	return;
}

link(x,y)

功能：加一条边$(x,y)$（在有出现环的时候忽略操作）

出现环（即xy原来就联通）可以用findroot判掉
否则，先makeroot(x)，然后把f(x)指向y即可
记得按需要更新y的信息！

inline void link(int x,int y) {
	makeroot(x);
	if(findroot(y)==x) return;
	f[x]=y;pushup(y);
	//printf("link: %d -> %d\n",x,y);
}

cut(x,y)

功能：切断边$(x,y)$（在没有这条边时忽略操作）

先makeroot(x)，然后access(y)，splay(y)到根
此时如果存在这条边，必然x和y是在同一个splay中
判断的充要条件：x是y的左儿子且x没有右儿子，比较显然
如果存在的话，把这条y的左儿子和x的父亲赋值为0即可
不要忘记更新y的信息（又一次）

inline void cut(int x,int y) {
	makeroot(x);access(y);splay(y);
	if(tr[y][0]!=x||tr[x][1]) return;
	tr[y][0]=f[x]=0;pushup(y);
	return;
}

pushdown(x)

大部分时候只需要翻转
一个看到的地方都说比较“稳妥”的写法
（谁不喜欢稳妥呢）

inline void tag(int x) {
	if(x) {
		rev[x]^=1;
		swap(tr[x][0],tr[x][1]);
	}
}
inline void pushdown(int x) {
	if(rev[x]){
		rev[x]=0;
		tag(tr[x][0]);
		tag(tr[x][1]);
	}
	return;
}

完整代码

经验传送门

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+100;
const int mod=1e9+7;
const double eps=1e-9;
inline ll read() {
	ll x(0),f(1);
	char c=getchar();
	while(!isdigit(c)) {
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)) {
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}

int n,m;

#define ls(o) tr[o][0]
#define rs(o) tr[o][1]
int tr[N][2],f[N],rev[N],val[N],mx[N];
inline bool isroot(int x) {
	return tr[f[x]][0]!=x&&tr[f[x]][1]!=x;
}
inline bool which(int x) {
	return tr[f[x]][1]==x;
}
inline void pushup(int x) {
	if(x){
		mx[x]=x;
		if(ls(x)&&val[mx[ls(x)]]>val[mx[x]]) mx[x]=mx[ls(x)];
		if(rs(x)&&val[mx[rs(x)]]>val[mx[x]]) mx[x]=mx[rs(x)];
	}
	return;
}
inline void tag(int x) {
	if(x) {
		rev[x]^=1;
		swap(tr[x][0],tr[x][1]);
	}
}
inline void pushdown(int x) {
	if(rev[x]){
		rev[x]=0;
		tag(tr[x][0]);
		tag(tr[x][1]);
	}
	return;
}
void debug(int x) {
	if(!x) return;
	pushdown(x);
	debug(tr[x][0]);
	printf("debug: x=%d ls=%d rs=%d\n",x,tr[x][0],tr[x][1]);
	debug(tr[x][1]);
	return;
}
inline void rotate(int x) {
	int fa=f[x],gfa=f[fa];
	int d=which(x),son=tr[x][d^1];
	f[x]=gfa;if(!isroot(fa)) tr[gfa][which(fa)]=x;
	f[fa]=x;tr[x][d^1]=fa;
	if(son){f[son]=fa;}tr[fa][d]=son;
	pushup(fa);pushup(x);
	return;
}
int zhan[N];
inline void splay(int x) {
	int y=x,top=0;
	zhan[++top]=y;
	while(!isroot(y)) zhan[++top]=y=f[y];
	while(top) pushdown(zhan[top--]);
	for(int fa; fa=f[x],!isroot(x); rotate(x)) {
		if(!isroot(fa)) which(fa)==which(x)?rotate(fa):rotate(x);
	}
	return;
}
inline void access(int x) {
	for(int y(0); x; y=x,x=f[x]) {
		splay(x);tr[x][1]=y;pushup(x);
		if(y) f[y]=x;
	}
	return;
}
inline void makeroot(int x) {
	access(x);splay(x);tag(x);
	return;
}
inline int findroot(int x) {
	access(x);splay(x);
	while(pushdown(x),tr[x][0]) x=tr[x][0];
	splay(x);
	return x;
}
inline void link(int x,int y) {
	makeroot(x);
	if(findroot(y)==x) return;
	f[x]=y;pushup(y);
	//printf("link: %d -> %d\n",x,y);
}
inline void cut(int x,int y) {
	makeroot(x);access(y);splay(y);
	if(tr[y][0]!=x||tr[x][1]) return;
	tr[y][0]=f[x]=0;pushup(y);
	return;
}
inline void split(int x,int y){//y is father
	makeroot(x);access(y);splay(y);
	return;
}