liuchanglc：Link Cut Tree学习笔记

当前位置博文首页 > liuchanglc：Link Cut Tree学习笔记

最大化缩小

liuchanglc：Link Cut Tree学习笔记

作者：liuchanglc 时间：2021-01-18 18:04

定义

动态树问题，是一类要求维护一个有根树森林，支持对树的分割, 合并等操作的问题。

由 \(RobertE.Tarjan\) 为首的科学家们提出解决算法 \(Link-Cut Trees\)，简称 \(lct\)。

在处理树上的很多询问问题的时候，我们常常会用到轻重链剖分，但是它只能维护当树的形态保持不变的时候的信息。

那么在树形态发生变化的时候，轻重链剖分就失去了效果，这个时候我们就要用到 \(lct\)。

个人感觉这篇博客讲的不错

前置知识:spaly

\(splay\) 是 \(lct\) 的辅助树

如果不会 \(splay\) 可以去我的博客学习一下

性质

\(1\)、和轻重链剖分相同的是，\(lct\) 也对要维护的树进行了划分，将链分为了实链和虚链。

每一个 \(Splay\) 维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历 \(Splay\) 得到的每个点的深度序列严格递增。

\(2\)、每个节点包含且仅包含于一个 \(Splay\) 中

\(3\)、边分为实边和虚边，实边包含在 \(Splay\) 中，而虚边总是由一棵 \(Splay\) 指向另一个节点（指向该 \(Splay\) 中中序遍历最靠前的点在原树中的父亲）。

如果一个节点有多个儿子，那么该节点只会认用实边相连的那个儿子，对于虚边相连的儿子，则会认父不认子。

操作

1、结构体定义

个人的写法是把 \(lct\) 封装到了结构体里

int ch[maxn][2],fa[maxn],val[maxn],sum[maxn],top,sta[maxn],rev[maxn];
//ch[0/1]:左/右儿子  fa:父亲节点 val:该节点的权值 
//sum:该节点及其子树的权值之和 sta&top:push_down时用 rev:翻转标记

2、标记上传和下放

类似于线段树

要注意的是，线段树的父亲节点并不是一个真实的节点，而 \(spaly\) 的父亲节点代表了原树中真实存在的一个节点

void push_up(rg int da){
	sum[da]=sum[ch[da][0]]^sum[ch[da][1]]^val[da];
}
void push_down(rg int da){
	rg int lc=ch[da][0],rc=ch[da][1];
	if(rev[da]){
		rev[lc]^=1,rev[rc]^=1,rev[da]^=1;
		std::swap(ch[da][0],ch[da][1]);
	}
}

3、isroot操作

判断某个节点是否是该节点所在的 \(splay\) 的根节点

利用了性质 \(3\)

bool isroot(rg int da){
	return (ch[fa[da]][0]!=da)&&(ch[fa[da]][1]!=da);
}

4、splay操作

和 \(splay\) 板子的区别就是多了 \(push\_down\) 操作

void xuanzh(rg int x){
	rg int y=fa[x];
	rg int z=fa[y];
	rg int k=(ch[y][1]==x);
	if(!isroot(y)){
		ch[z][ch[z][1]==y]=x;
	}
	fa[x]=z;
	ch[y][k]=ch[x][k^1];
	fa[ch[x][k^1]]=y;
	ch[x][k^1]=y;
	fa[y]=x;
	push_up(y);
	push_up(x);
}
void splay(rg int x){
	sta[top=1]=x;
	for(rg int i=x;!isroot(i);i=fa[i]) sta[++top]=fa[i];
	for(rg int i=top;i>=1;i--) push_down(sta[i]);
    //把需要下传标记的提前存起来一起修改
	while(!isroot(x)){
		rg int y=fa[x];
		rg int z=fa[y];
		if(!isroot(y)){
			(ch[z][1]==y)^(ch[y][1]==x)?xuanzh(x):xuanzh(y);
		}
		xuanzh(x);
	}
}

5、access操作

比较重要的一个操作

目的是打通根节点到指定节点的实链，使得一条中序遍历以根开始、以指定点结束的 \(Splay\) 出现

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

6、makeroot操作

使某一个节点成为整个联通块的根

\(access\) 之后已经打通了一条当前点到根节点的路径

此时 \(x\) 在 \(Splay\) 中一定是深度最大的点

把 \(x\ splay\) 一下，\(x\) 将没有右子树（性质\(1\)）

于是翻转整个 \(Splay\)，使得所有点的深度都倒过来了

\(x\) 没了左子树，成了深度最小的点（根节点），达到了我们的目的

要注意的是，换根操作之后，原树的形态就改变了

void makeroot(rg int x){
	access(x);
	splay(x);
	rev[x]^=1;
	push_down(x);
}

7、findroot操作

找出指定点所在的联通块的根节点

和上一个操作一样，只不过这一次我们不再进行翻转操作，而是一直跳左子树

最后跳到的节点就是根

int findroot(rg int x){
	access(x);
	splay(x);
	while(ch[x][0]){
		push_down(x);
		x=ch[x][0];
	}
	splay(x);
	return x;
}

8、split操作

提取 \(x\) 到 \(y\) 的路径

先让 \(x\) 成为根节点，再打通 \(y\) 到根节点的路径

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

9、删边、连边操作

先让 \(x\) 成为根节点，再判断联通性

void link(rg int x,rg int y){
	makeroot(x);
	if(findroot(y)!=x) fa[x]=y;
}
void cut(rg int x,rg int y){
	makeroot(x);
	if(findroot(y)==x && fa[y]==x && ch[y][0]==0){
		fa[y]=ch[x][1]=0;
		push_up(x);
	}
}

10、求LCA操作

两遍 \(access\)

int access(rg int x){
   for(rg int y=0;x;y=x,x=fa[x]){
   	splay(x);
   	ch[x][1]=y;
   	push_up(x);
   }
   return y;// 多了一个返回值
}

然后求 \(LCA\) 的过程就出来了。

int LCA(int x,int y){ 
   if(findroot(x)!=findroot(y))// 必须的特判。
   	return -1;
   access(x);
   return access(y); 
}

完整模板

洛谷P3690

#include<cstdio>
#include<iostream>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=1e6+5;
int n,m;
struct LCT{
	int ch[maxn][2],fa[maxn],val[maxn],sum[maxn],top,sta[maxn],rev[maxn];
	void push_up(rg int da){
		sum[da]=sum[ch[da][0]]^sum[ch[da][1]]^val[da];
	}
	void push_down(rg int da){
		rg int lc=ch[da][0],rc=ch[da][1];
		if(rev[da]){
			rev[lc]^=1,rev[rc]^=1,rev[da]^=1;
			std::swap(ch[da][0],ch[da][1]);
		}
	}
	bool isroot(rg int da){
		return (ch[fa[da]][0]!=da)&&(ch[fa[da]][1]!=da);
	}
	void xuanzh(rg int x){
		rg int y=fa[x];
		rg int z=fa[y];
		rg int k=(ch[y][1]==x);
		if(!isroot(y)){
			ch[z][ch[z][1]==y]=x;
		}
		fa[x]=z;
		ch[y][k]=ch[x][k^1];
		fa[ch[x][k^1]]=y;
		ch[x][k^1]=y;
		fa[y]=x;
		push_up(y);
		push_up(x);
	}
	void splay(rg int x){
		sta[top=1]=x;
		for(rg int i=x;!isroot(i);i=fa[i]) sta[++top]=fa[i];
		for(rg int i=top;i>=1;i--) push_down(sta[i]);
		while(!isroot(x)){
			rg int y=fa[x];
			rg int z=fa[y];
			if(!isroot(y)){
				(ch[z][1]==y)^(ch[y][1]==x)?xuanzh(x):xuanzh(y);
			}
			xuanzh(x);
		}
	}
	void access(rg int x){
		for(rg int y=0;x;y=x,x=fa[x]){
			splay(x);
			ch[x][1]=y;
			push_up(x);
		}
	}
	void makeroot(rg int x){
		access(x);
		splay(x);
		rev[x]^=1;
		push_down(x);
	}
	int findroot(rg int x){
		access(x);
		splay(x);
		while(ch[x][0]){
			push_down(x);
			x=ch[x][0];
		}
		splay(x);
		return x;
	}
	void split(rg int x,rg int y){
		makeroot(x);
		access(y);
		splay(y);
	}
	void link(rg int x,rg int y){
		makeroot(x);
		if(findroot(y)!=x) fa[x]=y;
	}
	void cut(rg int x,rg int y){
		makeroot(x);
		if(findroot(y)==x && fa[y]==x && ch[y][0]==0){
			fa[y]=ch[x][1]=0;
			push_up(x);
		}
	}
}lct;
int main(){
	n=read(),m=read();
	for(rg int i=1;i<=n;i++) lct.sum[i]=lct.val[i]=read();
	rg int aa,bb,cc;
	for(rg int i=1;i<=m;i++){
		aa=read(),bb=read(),cc=read();
		if(aa==0){
			lct.split(bb,cc);
			printf("%d\n",lct.sum[cc]);
		} else if(aa==1){
			lct.link(bb,cc);
		} else if(aa==2){
			lct.cut(bb,cc);
		} else {
			lct.splay(bb);
			lct.val[bb]=cc;
		}
	}
	return 0;
}

复杂度证明

传送门

一些题目

类型一、维护链信息

[国家集训队]Tree II

注意区间标记先乘后除

然后就和普通的线段树一样标记下放即可

如果没有删边和加边操作，也可以用树链剖分实现，但是复杂度要多一个 \(log\)

有的时候要维护的信息不是在点上而是在边上

此时我们就需要把边看成点

例如有一条边 \((u,v)\)，编号为 \(id\)

那么我们需要在 \(lct\) 中连两条边 \((u,id+n)(v,id+n)\)

边的信息储存在 \(id+n\) 这个点上

类型二、动态维护联通性

[SDOI2008]洞穴勘测

用可撤销并查集按秩合并也可以做

换成 \(lct\) 也是一个板子

只要判断两个点 \(findroot\) 得到的值是否一样即可

长跑

由于图中会出现边双，不能重复计算，所以需要将边双缩点

用并查集维护当前的点属于哪一个双联通分量

考虑合并 \(x\) 到 \(y\) ，如果 \(x\) 和 \(y\) 在 \(lct\) 上不是联通的，那么直接连边

否则我们先取出 \(x\) 到 \(y\) 的路径，将路径上所有权值都加到 \(y\) 上，同时把路径上所有点的父亲设为 \(y\)

要注意的是每次操作之前都要在并查集里找一下祖先

类型三、最小生成树一类的问题

最小差值生成树

[NOI2014]魔法森林

[Cnoi2019]须臾幻境

[WC2006]水管局长

这种题大部分都需要在边权上维护一个最大/最小值，然后按照边权从大到小/从小到大排序

遍历到一条边时，如果这条边所连的两个点已经在同一个同一个联通块中，根据需要删边/加边

类型四、维护子树信息

P4219 [BJOI2014]大融合

因为 \(LCT\) 中的儿子有实儿子和虚儿子之分

\(splay\) 中存储的只是实儿子的信息

所以我们要新开一个变量 \(siz2\) 记录虚子树的大小

相应地一些函数也要被修改

struct LCT{
	int ch[maxn][2],siz2[maxn],siz[maxn],top,sta[maxn],rev[maxn],wz[maxn],fa[maxn];
	void push_up(rg int da){
		siz[da]=siz[ch[da][1]]+siz[ch[da][0]]+1+siz2[da];//1
	}
	void push_down(rg int da){
		rg int lc=ch[da][0],rc=ch[da][1];
		if(rev[da]){
			rev[lc]^=1,rev[rc]^=1,rev[da]^=1;
			std::swap(ch[da][0],ch[da][1]);
		}
	}
	bool isroot(rg int da){
		return ch[fa[da]][0]!=da&&ch[fa[da]][1]!=da;
	}
	void xuanzh(rg int x){
		rg int y=fa[x];
		rg int z=fa[y];
		rg int k=(ch[y][1]==x);
		if(!isroot(y)){
			ch[z][ch[z][1]==y]=x;
		}
		fa[x]=z;
		ch[y][k]=ch[x][k^1];
		fa[ch[x][k^1]]=y;
		ch[x][k^1]=y;
		fa[y]=x;
		push_up(y);
		push_up(x);
	}
	void splay(rg int x){
		top=1;
		sta[top]=x;
		for(rg int i=x;!isroot(i);i=fa[i]) sta[++top]=fa[i];
		for(rg int i=top;i>=1;i--) push_down(sta[i]);
		while(!isroot(x)){
			rg int y=fa[x];
			rg int z=fa[y];
			if(!isroot(y)){
				(ch[z][1]==y)^(ch[y][1]==x)?xuanzh(x):xuanzh(y);
			}
			xuanzh(x);
		}
	}
	void access(rg int x){
		for(rg int y=0;x;y=x,x=fa[x]){
			splay(x);
			siz2[x]+=siz[ch[x][1]]-siz[y];//2
			ch[x][1]=y;
			push_up(x);
		}
	}
	void makeroot(rg int x){
		access(x);
		splay(x);
		rev[x]^=1;
		push_down(x);
	}
	void split(rg int x,rg int y){
		makeroot(x);
		access(y);
		splay(y);
	}
	void link(rg int x,rg int y){
		makeroot(x);
		makeroot(y);
		fa[x]=y;
		siz2[y]+=siz[x];//3
	}
	void cut(rg int x,rg int y){
		split(x,y);
		fa[x]=ch[y][0]=0;
		push_up(y);
		makeroot(x);
		makeroot(y);
	}
}lct;

类型五、查询k级祖先

loj#6710. 「RCOI2019」维护

若设每个点的点权均为 \(1\)，删除时把点权置为 \(0\)

则这样得到的 \(k\) 级祖先就是到这个点的路径上权值和为 \(k\) 的祖先

所以在 \(lct\) 上二分查找即可

代码

int find(rg int now,rg int ke){
	access(now);
	splay(now);
	if(!now || sum[ch[now][0]]<ke) return 0;
	if(ke==0) return now;
	now=ch[now][0];
	while(now){
		if(sum[ch[now][1]]>=ke) now=ch[now][1];
		else if(sum[ch[now][1]]+val[now]==ke) return splay(now),now;
		else {
			ke-=(sum[ch[now][1]]+val[now]);
			now=ch[now][0];
		}
	}
	return 233;
}

上一篇：朱昆：🎉 Element UI for Vue 3.0 来了！

下一篇：没有了

立即下载 - IIS7 站长工具包