[模板] 动态树 LCT

2024-02-05 12:06:04

[模板] 动态树 LCT

今天终于把这东西学会了。

~~比大模拟还难写。~~

概念类

Link-Cut-Tree 是用来解决 动态树 问题的一种数据结构。
类似于轻重链剖分，这里使用 虚实链剖分 ，同时利用 Splay 灵活多变的性质来维护动态操作，其中 每一条实链都用一棵 Splay 来维护。（也叫作 Auxiliary Tree(辅助树)）
- 基本思想可以概括为：“只认父亲，不认儿子” 。
- 也就是说对于任意一个非根节点，记录它的父亲和它的 唯一的重儿子。

辅助树的一些注意要点：

分清”假根“和“真根”：
- 假根：辅助树的根。
- 真根：整棵原图树的根。
辅助树的键值为 每个节点的深度，也就是说辅助树的中序遍历的节点的深度是 严格单调递增 的。
对于辅助树的根 \(rt\)，让 \(rt\) 与辅助树内的中序遍历的第一个点在原树上的 father 连单向边（也是虚边），这样辅助树和原图就连接起来了。

原树与辅助树的区别：@Candy

具体操作

Splay 基本操作

需要考虑懒标记的影响。

判断是不是假根也和原来有区别：

inline bool nroot(int x){
	return son[fa[x]][0]==x || son[fa[x]][1]==x;//只认重儿子，也是和普通Splay的区别
}

inline void rotate(int x){
	int y=fa[x],z=fa[y];
	bool rsx=rson(x),rsy=rson(y);
	if(nroot(y))son[z][rsy]=x;
	son[y][rsx]=son[x][!rsx];
	son[x][!rsx]=y;
	fa[son[y][rsx]]=y;fa[y]=x;fa[x]=z;
	pushup(y);
}
void splay(int x){
	top=0;int y=x,z=0;
	stk[++top]=y;
	while(nroot(y))stk[++top]=fa[y],y=fa[y];//因为是从上到下，所以用栈
	while(top)pushdown(stk[top--]);//warning!
	while(nroot(x)){
		y=fa[x];
		if(nroot(y))rotate((rson(x)^rson(y))?x:y);
		rotate(x);
	}
	pushup(x);
}

access

核心操作：把一个点到树的根的树链打通为实链。

本质上还是一个 Splay 合并的过程，或者说是一个不断丢弃右儿子的过程（因为向上合并，深度递减，只能接到右儿子上）。

这里注意：打通后的 Splay 的根节点是无法确定的，并不是一条链的结构，因为辅助树右子树丢掉了，但左子树也许存在。

这也就是说：尽量每次操作后如果有必要的话，都 Splay 当前节点调整树的结构，维持其复杂度。

~~至于为什么会WA，我也不清楚~~

具体来说做法就是想上找 \(fa\) 然后合并就行了。

void access(int x){//打通到（真）根
	for(int y=0;x;y=x,x=fa[x]){
		splay(x);son[x][1]=y;pushup(x);
	}
}

makeroot

让当前点变成原树的根节点。

可以先打通到根的路径，然后让 \(x\) 成为辅助树根节点，然后进行 颠倒+打 tag 操作。

inline void makeroot(int x){//换（真）根
	access(x);splay(x);
	pushr(x);
}

findroot

找到当前节点所在 连通块 的树的根。（因为 LCT 经典应用就是维护森林）

也是先打通，再 \(splay(x)\)，然后一直往左子树走找深度最小的点，最后得到的点就是根节点。

注意处理 tag 。

至于最后为什么要 \(splay\) 一下，网上说法大不相同。

UPdated on 2021/7/11

之所以最后要 \(splay\) 一下是因为在 cut 操作的时候会出问题，要保证 findroot 的结点的 fa 最后不能为 0 。

int findroot(int x){//找（真）根
	access(x);splay(x);
	while(son[x][0])pushdown(x),x=son[x][0];
	splay(x);//调整形态，保证复杂度 ?? 也许大概率是因为 pushdown 的问题。
	return x;
}

split

把一条链 \((x,y)\) 拎出来，或者说这才是应用的操作。

可以先让 \(x\) 成为根节点，然后打通 \(y\) 到根节点的路径，最后 \(splay(y)\) 。

inline void split(int x,int y){
	makeroot(x);access(y);splay(y);//y是根
}

link

特判有没有在一个连通块内即可。

inline void link(int x,int y){
	makeroot(x);
	if(findroot(y)!=x)fa[x]=y;
}

cut

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

总代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
	T x=0;char ch=getchar();bool fl=false;
	while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
	}
	return fl?-x:x;
}
#define read() read<int>()
const int maxn = 1e5 + 10;
int n,m,val[maxn];
int fa[maxn],son[maxn][2],s[maxn],stk[maxn],top=0;
bool rev[maxn];
inline bool nroot(int x){
	return son[fa[x]][0]==x || son[fa[x]][1]==x;//只认重儿子，也是和普通Splay的区别
}
inline void pushr(int x){
	int tmp=son[x][0];son[x][0]=son[x][1];son[x][1]=tmp;
	rev[x]^=1;
}
inline void pushup(int x){
	s[x]=s[son[x][0]]^s[son[x][1]]^val[x];
}
inline void pushdown(int x){
	if(!rev[x])return ;
	if(son[x][0])pushr(son[x][0]);
	if(son[x][1])pushr(son[x][1]);rev[x]=0;
}
inline bool rson(int x){return x==son[fa[x]][1];}
inline void rotate(int x){
	int y=fa[x],z=fa[y];
	bool rsx=rson(x),rsy=rson(y);
	if(nroot(y))son[z][rsy]=x;
	son[y][rsx]=son[x][!rsx];
	son[x][!rsx]=y;
	fa[son[y][rsx]]=y;fa[y]=x;fa[x]=z;
	pushup(y);
}
void splay(int x){
	top=0;int y=x,z=0;
	stk[++top]=y;
	while(nroot(y))stk[++top]=fa[y],y=fa[y];
	while(top)pushdown(stk[top--]);//warning!
	while(nroot(x)){
		y=fa[x];
		if(nroot(y))rotate((rson(x)^rson(y))?x:y);
		rotate(x);
	}
	pushup(x);
}
void access(int x){//打通到（真）根
	for(int y=0;x;y=x,x=fa[x]){
		splay(x);son[x][1]=y;pushup(x);
	}
}
inline void makeroot(int x){//换（真）根
	access(x);splay(x);
	pushr(x);
}
int findroot(int x){//找（真）根
	access(x);splay(x);
	while(son[x][0])pushdown(x),x=son[x][0];
	splay(x);//调整形态 
	return x;
}
inline void split(int x,int y){
	makeroot(x);access(y);splay(y);//y是根
}
inline void link(int x,int y){
	makeroot(x);
	if(findroot(y)!=x)fa[x]=y;
}
inline void cut(int x,int y){
	makeroot(x);
	if(findroot(y)==x && fa[y]==x && !son[y][0]){
		fa[y]=son[x][1]=0;pushup(x);
	}
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++)val[i]=read();
	while(m--){
		int op=read(),x=read(),y=read();
		if(op==0)split(x,y),printf("%d\n",s[y]);
		if(op==1)link(x,y);
		if(op==2)cut(x,y);
		if(op==3)splay(x),val[x]=y;
	}
	return 0;
}

LCA

比如求 \((x,y)\) 的 LCA 。

可以先打通 \(x\) 到根节点的路径，再把辅助树的根节点设为 \(x\)。

这样最后再让 \(y\) 打通上去，当它跳到 \(LCA\) 的时候，因为要舍弃右子树，所以 \(LCA\) 到 \(x\) 这一段路径就不存在了，\(fa[LCA]=0\)，最后 \(access\) 的 \(y\) 就是 \(LCA\) 。

码农公寓