\(LCT\)基础知识

树上操作是算法竞赛中重要的操作

由于树的特殊性，使得维护一些子树信息和路径信息变得较为困难，

常见情况有如下几种：

修改两点间路径权值。
查询两点间路径权值和。
修改某点子树权值。
查询某点子树权值和。
断开并连接一些边，保证仍是一棵树。

常见的做法是将树线性化，即树链剖分。~~本蒟蒻至今没完全明白这玩意~~对于 \(LCT\) 来说并不是我们常见的重链剖分，也不是长链剖分，而是一种只会用在这里的新的剖分方式

但是前面学习的树链剖分只能解决静态树上的问题，如果树的形态发生了改变则无法完成，

这时候需要动态树，\(LCT(Link-Cut \ \ Tree)\) 孕育而生，当然还有啥 \(ETT,Top \ Tree\) 这些动态树

\(LCT\) 也是将某一个儿子的连边划分为实边，而连向其他子树的边划分为虚边，这种剖分称之为实链剖分。

实链剖分

我们可以任意选择一条通向儿子的边作为实边，其他的边为虚边，和别的剖分的区别在于虚实是可以动态变化的，因此要使用灵活的平衡树 \(Splay\) 来维护每一条由若干实边连接而成的实链。其中 \(Splay\) 也被称作辅助树。~~不会平衡树的同学请出门左转，话说不知道有没有别的平衡树做辅助树的。~~

辅助树

这里的每一棵 \(Splay\) 其实都是维护的一条原树上的实链。\(Splay\) 的根节点的父亲节点指向原树上这条链的根节点。这类父亲链接与通常 Splay 的父亲链接区别在于儿子认父亲，而父亲不认儿子，对应原树的一条虚边。 我们不需要维护原树，可以通过辅助树还原出原树

一些性质

原树中的实链 : 在辅助树中节点都在一棵 \(Splay\) 中。
原树中的虚链 : 在辅助树中，子节点所在 \(Splay\) 的根节点指向父节点，但是父节点的两个儿子都不指向子节点。
原树的根不等于辅助树的根。
原树的父亲指向不等于辅助树的父亲指向。
辅助树是可以在满足辅助树、\(Splay\) 的性质下任意换根的。
虚实链变换可以轻松在辅助树上完成，这也就是实现了动态维护树链剖分。

\(LCT\) 维护的对象其实是一个平衡树森林。在实链剖分的基础下，\(LCT\) 支持以下的操作：查询、修改链上的信息；随意指定原树的根（即换根）；动态连边、删边；合并、分离树；动态维护连通性……~~欢迎各位dalao补充~~

_{又臭又长的部分结束了}

\(LCT\) 基础操作

函数定义

\(LCT\)有以下的一些基本函数：

\(Access(x)\)：访问 \(x\) 结点，且将 \(x\) 到根节点的路径变为实链。必须实现
\(Findroot(x)\)：找 \(x\) 所在树中编号最小的结点
\(Rotate(x)\)：反转 \(x\) 点到根的这条链, 将 \(x\) 变为根
\(Makeroot(x)\)：使 \(x\) 变为当前树的根
\(Cut(x,y)\)：将结点 \(y\) 与其所在树中的父亲结点 \(x\) 之间的边删去，即以 \(y\) 为根的子树删去
\(Link(x,y)\)：添加一条边 \((x,y)\)，即 \(x\) 是 \(y\) 的父亲
\(Split(x,y)\)：提取出 \(x,y\) 间的路径
\(Splay(x)\)：平衡树的相关操作
\(Isroot(x)\)：判断 \(x\) 是否为其所在树的根，可能常写为 \(Nroot(x)\)，~~确实要简单些~~

函数实现

\(pushdown() \ \And\And \ pushup()\) 自己根据题目实现

\(Nroot()\) 很简单，利用 \(Splay\) 树根的父节点儿子不指向当前节点的性质判断

bool nroot(int x){
	return ch[f[x]][0]==x||ch[f[x]][1]==x;
}

\(Splay() \And\And Rotate()\) 其实就是平衡树上该咋写咋写，有点小改动

void rotate(int x){
	int y = f[x],z = f[y],k = ch[y][1]==x,w = ch[x][!k];
	if(nroot(y)) ch[z][ch[z][1]==y] = x;//注意这一句
	ch[x][!k] = y;
	ch[y][k] = w;
	if(w) f[w] = y;
	f[y] = x;
	f[x] = z;
	pushup(y);
}
void update(int p){
	if(nRoot(p)) update(f[p]);
	pushDown(p);
}
void splay(int x){
	int y = x,z = 0;
	st[++z] = y;
	while(nroot(y)) st[++z] = y = f[y];
	while(z) pushdown(st[z--]);
	//上面这部分有些人会单独写出来，就是update那段
	while(nroot(x)){
		y = f[x];
		z = f[y];
		if(nroot(y))
			rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		rotate(x);
	}
	pushup(x);
}

\(Access()\) 只有如下四步操作：

把当前节点转到根。
把儿子换成之前的节点。
更新当前点的信息。
把当前点换成当前点的父亲，继续操作。

void access(int x){
	for(int y = 0;x;x = f[y = x]){
		splay(x);
		rc = y;
		pushup(x);
	}
}

\(Makeroot()\) 其实也很好实现，只需要把当前点先 \(Access()\) 一边在用 \(Splay()\) 转至根节点

void pushr(int x){//按题目自己实现
	int t = lc;
	lc = rc;
	rc = t;
	r[x]^=1;
}
void makeroot(int x){
	access(x);
	splay(x);
	pushr(x);//这句自己看着办
}

\(Link()\) 记得判断是否是在同一棵树内

void link(int x,int y){
	makeroot(x);
	if(findroot(y)!=x) f[x] = y;
}
//oi-wiki上的写法，未附带判断
void Link(int x, int p) {
	makeRoot(x);
	splay(x);
	f[x] = p;
}

\(Split()\) 就是拿出一棵 Splay，维护 \(x\) 到 \(y\) 的路径。

可以直接把需要的路径拿出到 \(y\) 的子树上，可以进行其他操作。

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

\(Findroot()\) 查找的是原树的根，只用到前面说的辅助树中序遍历为原树上的链的性质便可以了，一直走左儿子到底就是根，\(Splay()\) 操作是来保证复杂度的

int findroot(int x){
	access(x);
	splay(x);
	while(lc){
		pushdown(x);
		x = lc;
	}
	splay(x);
	return x;
}

\(Cut()\) 也要记得判断是否合法，除非说了保证合法

需要满足以下条件：

二者连通
路径上没有其他的链
\(x\) 没有右儿子

void cut(int x,int y){
	makeroot(x);
	if(findroot(y)==x&&f[y]==x&&!ch[y][0]){
		f[y] = ch[x][1] = 0;
		pushup(x);
	}
}

以下是洛谷模板题代码：

#include<bits/stdc++.h>
#define lc ch[x][0]
#define rc ch[x][1]
#define N 300010
using namespace std;
int n,m,f[N],ch[N][2],val[N],s[N],st[N];
bool r[N];
bool nroot(int x){
	return ch[f[x]][0]==x||ch[f[x]][1]==x;
}
void pushup(int x){
	s[x] = s[lc]^s[rc]^val[x];
}
void pushr(int x){
	int t = lc;
	lc = rc;
	rc = t;
	r[x]^=1;
}
void pushdown(int x){
	if(r[x]){
		if(lc) pushr(lc);
		if(rc) pushr(rc);
		r[x] = 0;
	}
}
void rotate(int x){
	int y = f[x],z = f[y],k = ch[y][1]==x,w = ch[x][!k];
	if(nroot(y)) ch[z][ch[z][1]==y] = x;
	ch[x][!k] = y;
	ch[y][k] = w;
	if(w) f[w] = y;
	f[y] = x;
	f[x] = z;
	pushup(y);
}
void splay(int x){
	int y = x,z = 0;
	st[++z] = y;
	while(nroot(y)) st[++z] = y = f[y];
	while(z) pushdown(st[z--]);
	while(nroot(x)){
		y = f[x];
		z = f[y];
		if(nroot(y))
			rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		rotate(x);
	}
	pushup(x);
}
void access(int x){
	for(int y = 0;x;x = f[y = x]){
		splay(x);
		rc = y;
		pushup(x);
	}
}
void makeroot(int x){
	access(x);
	splay(x);
	pushr(x);
}
int findroot(int x){
	access(x);
	splay(x);
	while(lc){
		pushdown(x);
		x = lc;
	}
	splay(x);
	return x;
}
void split(int x,int y){
	makeroot(x);
	access(y);
	splay(y);
}
void link(int x,int y){
	makeroot(x);
	if(findroot(y)!=x) f[x] = y;
}
void cut(int x,int y){
	makeroot(x);
	if(findroot(y)==x&&f[y]==x&&!ch[y][0]){
		f[y] = ch[x][1] = 0;
		pushup(x);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i<=n;i++)
		scanf("%d",&val[i]);
	while(m--){
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		switch(op){
			case 0:
				split(x,y);
				printf("%d\n",s[y]);break;
			case 1:
				link(x,y);break;
			case 2:
				cut(x,y);break;
			case 3:
				splay(x);val[x] = y;break;
		}
	}
	return 0; 
}

完结撒花

以后再说补充习题的事