Link-Cut Tree 学习笔记

在众多数据结构,\(Link-Cut\ Tree\),或者叫作动态树,以其代码的长度著称,在学习了\(1\)天\(LCT\)并深深地被其恶心到之后,我决定口糊这样一篇学习笔记。

在学\(LCT\)之前,你需要先学会树链剖分与\(Splay\)。

定义及性质

树链剖分大家都知道,是可以用来解决树上路径、子树相关问题的方法,而\(LCT\)同样也可以很方便地结局路径相关问题以及一些子树的问题,但不同的是,它更加高级,可以支持动态连边、删边(也就是说大部分情况下动态树处理的是森林上的问题)。

相信大家都知道,重链剖分通过划分轻边与重边,然后用线段树等数据结构维护终边构成的重链,使得链上问题便于解决。

同样的,\(LCT\)我们也可以把它看成是一种实链剖分,即将每个点连向某一个儿子的边划分为实边,将连向其他子树的边划分为虚边。

之所以叫虚实,是为了突出虚边与实边能够不断动态变化的性质,也正因为这个,\(LCT\)使用更灵活的\(Splay\)来维护每一条实边构成的实链。

\(LCT\)维护的是许多棵\(Splay\)组成的森林,它们满足以下一些优秀性质:

  • 每个\(Splay\)维护的是一条深度单调递增的链(就是定义),并且它的中序遍历得到的节点序列深度单调递增且相邻的深度差为\(1\)
  • 每个节点被包含且仅包包含在一个\(Splay\)中
  • 所有的实边都连接着在同一个\(Splay\)中的两个点,虚边由一棵\(Splay\)的根指向另一个点(即该\(Splay\)中深度最小的点在原树中的父亲)
  • “认父不认子”:即每个点只向其中一个儿子连一条实链,所以是无法直接访问其他儿子的

各种操作

\(access(x)\)

access操作:拉通某个点到根节点的实链,并保存在一棵\(Splay\)中,即将路径上的虚边变成实边,将路径上的点连向儿子的其他实边变成虚边。

这里我们嫖了神仙的博客的图来讲解一下:

以下面这棵树为例,一开始实边虚边是这样划分的:

Link-Cut Tree 学习笔记

现在假设我们要\(access(N)\),拉出一条\(A-N\)的实链,即将原树变为;

Link-Cut Tree 学习笔记

一开始的时候,假设我们维护的是这样的\(Splay\):

Link-Cut Tree 学习笔记

那么我们一路向根处理,首先在\(N\)所在的\(Splay\)中,我们先\(Splay(N)\),接着,我们需要将\(N-O\)的实边变成虚边,因为\(LCT\)的认父不认子,我们直接将\(N\)的右儿子置为\(0\),于是这一部分的\(Splay\)就变成了:

Link-Cut Tree 学习笔记

继续向上处理,在\(I\)所在的\(Splay\)中,我们也将\(I\) \(Splay\)到根,首先要将\(I-K\)的实边变虚,然后将\(I-N\)的虚边变实,同样的,我们直接将\(I\)的右儿子置为\(N\)即可:

Link-Cut Tree 学习笔记

依次循环处理下去即可,事实上大致思路就是:

将\(x\ Splay\)到根,更新其右儿子为上一个遍历到的数,然后更新信息,继续向父亲处理:

inline void access(int x){
	for(int last=0;x;last=x,x=fa[x])
		Splay(x),ch[x][1]=last,pushup(x);
}//连出x到rt路径的splay 

\(makeroot(x)\)

makeroot操作:将\(x\)置为所在原树的根,也就是让它变成这棵树上深度最小的点,这样的操作显然不会影响到链上的操作,但却会影响子树的相关信息,导致\(LCT\)处理子树较为麻烦,不过那是后话。

我们先拉出\(x\)到根的\(Splay\),然后将\(x\) \(Splay\)到根,这时显然\(x\)是这棵\(Splay\)中深度最大的点,所以它没有右儿子,因此我们直接翻转这棵\(Splay\),就能让\(x\)变成深度最小的点,也就是根了.

如同文艺平衡树一样,我们对每个节点维护一个\(rev\)标记并下传即可:

inline void pushdown(int x){
	if(!rev[x]) return ;
	if(ch[x][0]) rever(ch[x][0]);
	if(ch[x][1]) rever(ch[x][1]);
	rev[x]=0;
} 
inline void makeroot(int x){
	access(x);Splay(x);
	rever(x);	
}//让x成为所在树的根 

\(findroot(x)\)

findroot操作:找到\(x\)所在原树的根:

因为根是这棵树种深度最小的节点,所以直接打通\(x\)到根的实链,将\(x\)到根,然后不断地跳左儿子即可

当然不要忘记\(pushdown\)

inline int findroot(int x){
	access(x);Splay(x);
	while(ch[x][0]) pushdown(x),x=ch[x][0];
	Splay(x);//Splay以保证复杂度
	return x;
}//找出x所在原树的根(深度最小的点) 

\(link(x,y)\)

link操作:在\(x,y\)之间连一条轻边,如果\(x,y\)在同一联通块则不用连边:把\(x\)置为所原树的根,然后直接将\(x\)的父亲置为\(y\)即可。

判断是否在同一个连通块就直接看\(findroot(y)\)是否\(=x\)即可:

inline void link(int x,int y){
	makeroot(x);
	if(findroot(y)==x) return ;//已经联通 
	fa[x]=y;
}//让x成为原树的根,向y连一条虚边 

\(cut(x,y)\)

cut操作:将\(x,y\)间的边断开,如果保证断边合法那么直接将\(x\)置为根,那么\(y\)一定是\(x\)的右儿子,于是直接更改\(x\)的右儿子与\(y\)的父亲即可。

判断断边合法,首先要\(x\)与\(y\)在同一棵\(Splay\)中,即\(findroot(y)==x\)

然后如果原树中\(x,y\)之间有边,那么它们一定在\(Splay\)中\(x,y\)之间或在\(y\)的左儿子中,于是再判断\(x\)的父亲是\(y\)且\(y\)左儿子为空即可:

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

\(split(x,y)\)

split操作:将\(x,y\)间的链变为实链且放在一个\(Splay\)中,以\(y\)为根:

直接将\(x\)置为根,然后拉出\(y\)到根的路径再\(Splay(y)\)即可:

inline void split(int x,int y){
	makeroot(x);
	access(y);Splay(y);
}//将x到y的链拉成一个splay,y成为这个splay的根 

除此之外,\(LCT\)中的\(Rotate\),\(Splay\)操作也与一般的\(Splay\)不同:

首先,这里面\(Splay\)是否已经到根不能再通过\(fa\)为\(0\)判断了,因为它的\(fa\)可能指向的是虚边连向的\(fa\),我们利用\(LCT\)的认父不认子来判断:

inline bool isroot(int x){
	return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}//LCT认父不认子,所以如果x的父亲找不到x就说明这是一条虚边,x是所在splay的根 

\(Rotate\)时也要额外判断是否更改了这棵\(Splay\)以外的点的东西:

inline void Rotate(int x){
	int y=fa[x],z=fa[y],wx=which(x),wy=which(y);
	if(!isroot(y)) ch[z][wy]=x;fa[x]=z;//如果y是rt,那么y-z是一条轻边,不应该更改z的儿子
	ch[y][wx]=ch[x][wx^1];
	if(ch[y][wx]) fa[ch[y][wx]]=y;
	ch[x][wx^1]=y;fa[y]=x;
	pushup(y);
}

\(Splay\)时,注意先将要经过的点全部\(pushdown\)一遍:

int stk[N];
inline void Splay(int x){
	int now=x,top=0;
	stk[++top]=now;
	while(!isroot(now)) now=fa[now],stk[++top]=now;
	while(top) pushdown(stk[top--]);
	while(!isroot(x)){
		int y=fa[x];
		if(!isroot(y)){
			if(which(x)==which(y)) Rotate(y);
			else Rotate(x);
		}
		Rotate(x);
	}
	pushup(x);
}

以上就是\(LCT\)一般的操作了。

例题

洛谷模板

直接把上面的操作串起来就行了,每个节点维护它所在\(Splay\)中子树的异或和,询问时将\(x,y\)的链拉出来,然后直接输出\(y\)维护的答案即可:

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,m;
int fa[N],ch[N][2],rt,val[N],sum[N],rev[N];
inline bool which(int x){return ch[fa[x]][1]==x;}
inline void pushup(int i){
	sum[i]=sum[ch[i][0]]^val[i]^sum[ch[i][1]];
}
inline bool isroot(int x){
	return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}//LCT认父不认子,所以如果x的父亲找不到x就说明这是一条虚边,x是所在splay的根 
inline void rever(int x){
	swap(ch[x][0],ch[x][1]);
	rev[x]^=1;
}
inline void pushdown(int x){
	if(!rev[x]) return ;
	if(ch[x][0]) rever(ch[x][0]);
	if(ch[x][1]) rever(ch[x][1]);
	rev[x]=0;
} 
inline void Rotate(int x){
	int y=fa[x],z=fa[y],wx=which(x),wy=which(y);
	if(!isroot(y)) ch[z][wy]=x;fa[x]=z;
	ch[y][wx]=ch[x][wx^1];
	if(ch[y][wx]) fa[ch[y][wx]]=y;
	ch[x][wx^1]=y;fa[y]=x;
	pushup(y);
}
int stk[N];
inline void Splay(int x){
	int now=x,top=0;
	stk[++top]=now;
	while(!isroot(now)) now=fa[now],stk[++top]=now;
	while(top) pushdown(stk[top--]);
	while(!isroot(x)){
		int y=fa[x];
		if(!isroot(y)){
			if(which(x)==which(y)) Rotate(y);
			else Rotate(x);
		}
		Rotate(x);
	}
	pushup(x);
}

inline void access(int x){
	for(int last=0;x;last=x,x=fa[x])
		Splay(x),ch[x][1]=last,pushup(x);
}//连出x到rt路径的splay 
inline void makeroot(int x){
	access(x);Splay(x);
	rever(x);	
}//让x成为所在树的根 
inline int findroot(int x){
	access(x);Splay(x);
	while(ch[x][0]) pushdown(x),x=ch[x][0];
	Splay(x);
	return x;
}//找出x所在原树的根(深度最小的点) 
inline void split(int x,int y){
	makeroot(x);
	access(y);Splay(y);
}//将x到y的链拉成一个splay,y成为这个splay的根 

inline void link(int x,int y){
	makeroot(x);
	if(findroot(y)==x) return ;//已经联通 
	fa[x]=y;
}//让x成为原树的根,向y连一条虚边 
inline void cut(int x,int y){
	makeroot(x);
	if(findroot(y)!=x||fa[y]!=x||ch[y][0]) return ;
	fa[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]);
	for(int i=1,op,x,y;i<=m;++i){
		scanf("%d%d%d",&op,&x,&y);
		if(op==0){
			split(x,y);
			printf("%d\n",sum[y]);
		}
		else if(op==1) link(x,y);
		else if(op==2) cut(x,y);
		else if(op==3){
			Splay(x);
			val[x]=y;
		}
	} 
	return 0;
}

更多好题:下篇博客更

上一篇:【14】shell:生成随机数


下一篇:Python分词库jieba快速入门