526互联

LCT学习笔记

发布时间 2023-11-10 16:13:27作者: shAdomOvO

LCT学习笔记

LCT，（Link Cut Tree） ，是一种动态树，维护的是森林。可以维护作有两点连通性，两点路径权值和，连接两点和切断某条边、修改信息等。

LCT是用Splay来维护的。每颗Splay维护的是原森林中的一条路径。

  • 性质一：Splay还要维护一个性质，那就是每颗Splay的中序遍历是原树中的一条从上到下的路径。（也就是深度递增的序列）再具体来说，Splay中的每个节点，左儿子是他的父亲，右儿子是他的儿子，如果他是父亲的左儿子，那他就是深度更深的节点（并不一定是直接的）。

而Splay是用实链剖分来划分的。也就是每个点向他的某个儿子连实边，向其它的儿子连虚边。

  • 性质二：每颗Splay并不是独立的，每颗Splay的根节点指向原树中这条链的父亲节点（即原树中这条链的最顶端的父亲节点）。需要注意的是，这连接的是虚边。

算了，不说这么多，我也不太理解，直接讲代码把。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=400011;
struct node{
	int fa,ch[2],val,sum,tag;
}t[N];
int isroot(int u){
	return t[t[u].fa].ch[0]==u||t[t[u].fa].ch[1]==u;
	//判断一个点是不是这颗Splay的根节点 
}
void pushup(int u){
	t[u].sum=t[t[u].ch[0]].sum^t[t[u].ch[1]].sum^t[u].val;
	//上传节点信息 
}
void rever(int u){
	swap(t[u].ch[0],t[u].ch[1]);
	t[u].tag^=1;
	//旋转一个节点 
}
int get_son(int u){
	return t[t[u].fa].ch[1]==u;
	//判断一个点是他的父亲节点的那个儿子 
}
void pushdown(int u){
	if(t[u].tag){
		if(t[u].ch[0])rever(t[u].ch[0]);
		if(t[u].ch[1])rever(t[u].ch[1]);
		t[u].tag=0;
	}
	//下传标记 
}
void rotate(int u){
	int Y=t[u].fa;
	int R=t[Y].fa;
	int Yson=get_son(u);
	int B=t[u].ch[!Yson];
	if(isroot(Y))t[R].ch[get_son(Y)]=u;
	t[Y].ch[Yson]=B;
	t[u].ch[!Yson]=Y;
	if(B)t[B].fa=Y;
	t[Y].fa=u;
	t[u].fa=R;
	pushup(Y);
	pushup(u);
	//旋转一个节点 
}
int sta[N];
void splay(int u){
	int x=u,top=0;
	sta[++top]=x;
	while(isroot(x)){
		x=t[x].fa;
		sta[++top]=x;
	}
//	while(isroot(x))sta[++top]=x=t[x].fa;
//	while(top)pushdown(sta[top--]);
	while(top){
		pushdown(sta[top]);
		top--;
	}
	while(isroot(u)){//这个点还有父亲 
		int fa=t[u].fa;
		if(isroot(fa)){
			if(get_son(u)==get_son(fa))rotate(fa);
			else rotate(u);
		}
		rotate(u);
	}
	//将一个节点旋转到根节点 
}
void access(int u){
	for(int x=0;u;x=u,u=t[u].fa){
		splay(u);t[u].ch[1]=x;pushup(u);
	}
	//将一个点与原树的根节点的路径打通 
}
void makeroot(int u){
	access(u);
	splay(u);
	rever(u);
	//将一个点变成根节点，
	//先将这个点与根节点的路径打通，
	//通过access的过程可以知道，u不会有右儿子，且一直会是父亲的右儿子
	//所以他的中序遍历是最后一个，所以将他翻转一下就是第一个 
}
int findroot(int u){
	access(u);
	splay(u);
	while(t[u].ch[0])pushdown(u),u=t[u].ch[0];
	//一定要记得pushdown，所有向下的操作都是要pushdown的
	splay(u);//将根旋转回去
	return u;
	//看 u 所在的数的根是那个
	//先将他提到根节点，然后一直往左儿子走就好了 
}
void split(int x,int y){
	makeroot(x);
	access(y);
	splay(y);
	//将x到y的路径提出来，现将x变成根，y跟x联通后将y提到根节点就好
	//x到y的路径会变成一条实链，且这条实链也只包括x到y的路径
	//因为虚链认父不认子，所以只会包括这条链的信息 
}
void link(int x,int y){
	makeroot(x);
	if(findroot(y)!=x)t[x].fa=y;
	//连接 x y
	//现将x提到根节点，再查询一下，
	//不联通的话，直接将x的父亲设为y就好 ,因为x是根节点，所以没有影响 
}
void cut(int x,int y){
	makeroot(x);
	if(findroot(y)==x&&t[y].fa==x&&t[y].ch[0]==0){
		t[y].fa=t[x].ch[1]=0;
		pushup(x);
	}
	//解释一下为什么findroot不会改变树的结构
	//因为要满足要求的话，在makeroot(x) 的时候，x就已经是 y的父亲
	//
	//删除x到y的边
	//也是先将x提到根节点，要满足x到y之间有边的话，
	//一定会满足y的跟是x，y的父亲是x，y没有左儿子
	//性质1显然
	//性质2因为x，y之间有边，并且x被提到了根，所以y深度一定比x大，所以y一定x的儿子 
	//性质3 y也不能有左儿子，因为有左儿子就说明有点的深度比y小，这显然是不满足性质的 
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>t[i].val;
	for(int i=1;i<=m;i++){
		int opt,x,y;
		cin>>opt>>x>>y;
		if(opt==0){
			split(x,y);
			cout<<t[y].sum<<"\n";
		}
		if(opt==1){
			link(x,y);
		}
		if(opt==2){
			cut(x,y);
		}
		if(opt==3){
			splay(x);
			t[x].val=y;
		}
	}
}

应用

LCT求LCA

虽然感觉有点大材小用了，但LCT确实是可以求LCA的，而且还可以求动态的LCA。即可以支持动态加边，换根等LCT本生支持的操作。

其他的操作都保存，唯一要加的就是一个求LCA的函数。

我们先将 x 和根节点连起来。然后显然，y和x的LCA一定在x到根节点的这条实链上。我们保存access的操作，最后一个连向的节点，就是他们相交的节点，就是他们的LCA。

int lca(int x,int y){
	access(x);
	int lst;
	for(lst=0;y;lst=y,y=t[y].fa){
		splay(y);t[y].ch[1]=lst;
	}
	return lst;
}

复杂度的话，LCT的常数显然是很大的，测试后大概跟倍增的常数（实现比较优秀的倍增）一致，是树剖的一半。

码量不长，但是绝对算不上好调。平时还是没有太大必要写的。

维护链信息（LCT上的线段树操作）

P1501 [国家集训队] Tree II

支持的操作：加边，删边，链上加，链上乘，链上求和。

还记得LCT的 \(split\) 操作吗，很显然，我们只需要将这条链扒出来，然后对这条链进行正常的标记修改就好了。也就是对这条链的顶点进行标记修改就好。跟普通的线段树写法没有任何区别。

唯一跟普通LCT相比需要修改的就是 \(pushdown\) 要跟线段树一样下放标记就好。

#include<bits/stdc++.h>
using namespace std;
const int N=200011;
#define int long long
int n,q;
#define ls t[u].ch[0]
#define rs t[u].ch[1]
#define mod 51061
struct node{
	int fa,siz,taf,ch[2];
	int add,mul,sum,val,tag;
}t[N];
int get_son(int u){
	return t[t[u].fa].ch[1]==u;
}
void rever(int u){
	swap(t[u].ch[0],t[u].ch[1]);
	t[u].tag^=1;
}
int isroot(int u){
	return t[t[u].fa].ch[0]==u||t[t[u].fa].ch[1]==u;
}
void pushup(int u){
	t[u].sum=(t[ls].sum+t[rs].sum+t[u].val)%mod;
	t[u].siz=t[ls].siz+t[rs].siz+1;
}
void pushdown(int u){
	if(t[u].tag){
		rever(ls);
		rever(rs);
		t[u].tag=0;
	}
	if(t[u].mul!=1){
		t[ls].mul=t[ls].mul*t[u].mul%mod;
		t[rs].mul=t[rs].mul*t[u].mul%mod;
		t[ls].add=t[ls].add*t[u].mul%mod;
		t[rs].add=t[rs].add*t[u].mul%mod;
		t[ls].val=t[ls].val*t[u].mul%mod;
		t[rs].val=t[rs].val*t[u].mul%mod;
		t[ls].sum=t[ls].sum*t[u].mul%mod;
		t[rs].sum=t[rs].sum*t[u].mul%mod;
		t[u].mul=1;
	}
	if(t[u].add){
		t[ls].add=(t[ls].add+t[u].add)%mod;
		t[rs].add=(t[rs].add+t[u].add)%mod;
		t[ls].val=(t[ls].val+t[u].add)%mod;
		t[rs].val=(t[rs].val+t[u].add)%mod;
		t[ls].sum=(t[ls].sum+t[ls].siz*t[u].add)%mod;
		t[rs].sum=(t[rs].sum+t[rs].siz*t[u].add)%mod;
		t[u].add=0;
	}
}
void rotate(int u){
	int Y=t[u].fa;
	int R=t[Y].fa;
	int Yson=get_son(u);
	int Rson=get_son(Y);
	int B=t[u].ch[!Yson];
	if(isroot(Y))t[R].ch[Rson]=u;
	t[u].fa=R;
	t[B].fa=Y;
	t[Y].ch[Yson]=B;
	t[u].ch[!Yson]=Y;
	t[Y].fa=u;
	pushup(Y);
	pushup(u);
}
int sta[N];
void splay(int u){
	int top=0,x=u;
	sta[++top]=x;
	while(isroot(x)){
		x=t[x].fa;
		sta[++top]=x;
	}
	while(top){
		pushdown(sta[top]);
		top--;
	}
	while(isroot(u)){
		int fa=t[u].fa;
		if(isroot(fa)){
			if(get_son(u)==get_son(fa))rotate(fa);
			else rotate(u);
		}
		rotate(u);
	}
}
void access(int u){
	for(int x=0;u;x=u,u=t[u].fa){
		splay(u);t[u].ch[1]=x;pushup(u);
	}
}
int findroot(int u){
	access(u);
	splay(u);
	while(t[u].ch[0])pushdown(u),u=t[u].ch[0];
	splay(u);
	return u;
} 
void makeroot(int u){
	access(u);
	splay(u);
	rever(u);
}
void link(int x,int y){
	makeroot(x);
	if(findroot(y)!=x)t[x].fa=y;
}
void cut(int x,int y){
	makeroot(x);
	if(findroot(y)==x&&t[y].fa==x&&t[y].ch[0]==0){
		t[y].fa=t[x].ch[1]=0;
		pushup(x);
	}
}
void split(int x,int y){
	makeroot(x);
	access(y);
	splay(y);
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)t[i].siz=t[i].val=t[i].sum=t[i].mul=1;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		link(u,v);
	}
	for(int i=1;i<=q;i++){
		char opt;
		int u,v,c,x,y;
		cin>>opt;
		if(opt=='+'){
			cin>>u>>v>>c;
			split(u,v);
			t[v].add=(t[v].add+c)%mod;
			t[v].sum=(t[v].sum+t[v].siz*c)%mod;
			t[v].val=(t[v].val+c)%mod;
		}
		if(opt=='*'){
			cin>>u>>v>>c;
			split(u,v);
			t[v].mul=t[v].mul*c%mod;
			t[v].sum=t[v].sum*c%mod; 
			t[v].val=t[v].val*c%mod;
		}
		if(opt=='/'){
			cin>>u>>v;
			split(u,v);
			cout<<t[v].sum<<"\n";
		}
		if(opt=='-'){
			cin>>u>>v>>x>>y;
			cut(u,v);
			link(x,y);
		}
	}
}

P3203 [HNOI2010] 弹飞绵羊

弹力系数可以看做一条边，答案就是走到外面的点的边数。

考虑建立一个 n+1 号节点，答案就是从那条边就到 n+1 号节点的边数。

显然可以先把 n+1 号点到 i 号节点的边扒出来。答案就是这条路径的长度。这就很简单了。

#include<bits/stdc++.h>
using namespace std;
const int N=400011;
struct node{
	int siz,ch[2],fa,tag;
}t[N];
int get_son(int u){
	return t[t[u].fa].ch[1]==u;
}
int isroot(int u){
	return t[t[u].fa].ch[0]==u||t[t[u].fa].ch[1]==u;
}
#define ls t[u].ch[0]
#define rs t[u].ch[1]
void rever(int u){
	swap(t[u].ch[0],t[u].ch[1]);
	t[u].tag^=1;
}
void pushdown(int u){
	if(t[u].tag){
		rever(t[u].ch[0]);
		rever(t[u].ch[1]);
		t[u].tag=0;
	}
}
void pushup(int u){
	t[u].siz=t[ls].siz+t[rs].siz+1;
}
void rotate(int u){
	int Y=t[u].fa;
	int R=t[Y].fa;
	int Yson=get_son(u);
	int Rson=get_son(Y);
	int B=t[u].ch[!Yson];
	if(isroot(Y))t[R].ch[Rson]=u;
	t[u].fa=R;
	t[Y].ch[Yson]=B;
	t[B].fa=Y;
	t[u].ch[!Yson]=Y;
	t[Y].fa=u;
	pushup(Y);
	pushup(u);
}
int sta[N];
void splay(int u){
	int x=u,top=0;
	sta[++top]=x;
	while(isroot(x)){
		x=t[x].fa;
		sta[++top]=x;
	}
	while(top){
		pushdown(sta[top]);
		top--;
	}
	while(isroot(u)){
		int fa=t[u].fa;
		if(isroot(fa)){
			if(get_son(u)==get_son(fa))rotate(fa);
			else rotate(u);
		}
		rotate(u);
	}
}
void access(int u){
	for(int x=0;u;x=u,u=t[u].fa){
		splay(u);t[u].ch[1]=x;pushup(u);
	}
}
int findroot(int u){
	access(u);
	splay(u);
	while(t[u].ch[0])pushdown(u),u=t[u].ch[0];
	splay(u);
	return u;
}
void makeroot(int u){
	access(u);
	splay(u);
	rever(u);
}
void link(int x,int y){
	makeroot(x);
	if(findroot(y)!=x)t[x].fa=y;
}
void cut(int x,int y){
	makeroot(x);
	if(findroot(y)==x&&t[y].fa==x&&t[y].ch[0]==0){
		t[y].fa=t[x].ch[1]=0;
		pushup(x);
	}
}
void split(int x,int y){
	makeroot(x);
	access(y);
	splay(y);
}
int n,m,x[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n+1;i++)t[i].siz=1;
	for(int i=1;i<=n;i++){
		cin>>x[i];
		if(i+x[i]>n){
			link(i,n+1);
//			cout<<"link:"<<i<<" "<<n+1<<'\n';
		}
		else{
			link(i,i+x[i]);
//			cout<<"link:"<<i<<" "<<i+x[i]<<"\n";
		} 
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int opt,j,k;
		cin>>opt>>j;
		j++;
		if(opt==1){
			split(j,n+1);
			cout<<t[n+1].siz-1<<"\n";
		}
		else{
			cin>>k;
			cut(j,(j+x[j]>n?n+1:j+x[j]));
			x[j]=k;
			link(j,(j+x[j]>n?n+1:j+x[j]));
		}
	}
}

动态维护连通性&双联通分量

P3950 部落冲突

就是随便判一下连通性就好。判断一下根是不是就好。

维护链上的边权信息（生成树）

维护子树信息

P4219 [BJOI2014] 大融合

一条边的贡献很好求，就是他们的子树大小相乘。

所以问题就变成了求动态加边的情况下求子树大小。

这就需要维护子树信息的LCT了。

因为还有虚子树的存在，所以我们需要维护一个虚子树的信息。

设原子树的信息为 \(siz[x]\) ，虚子树的信息为 \(siz2[x]\) 。

考虑什么时候会改变边的虚实关系。

发现在 access 操作的时候会修改一个点的右儿子。这是我们就需要对他的 \(siz2[x]\) 进行修改。具体如下

void access(int u){
	for(int x=0;u;x=u,u=t[u].fa){
		splay(u);siz2[u]+=siz[t[u].ch[1]]-siz[x];pushup(u);
    }
}

然后就是在加边的时候也会影响到一个点的虚实关系。 link(x,y) 的话会使得 \(y\) 多一条虚边。这是可以将 \(y\) 的 \(siz2[y]+=siz[x]\) 就好。

然后其他的操作就跟普通的 LCT 一致就好。

#include<bits/stdc++.h>
using namespace std;
const int N=100011;
int n,q;
#define int long long
struct tree{
	int ch[2],siz,siz2,tag,fa;
}t[N];
int get_son(int u){
	return t[t[u].fa].ch[1]==u;
}
int isroot(int u){
	return t[t[u].fa].ch[0]==u||t[t[u].fa].ch[1]==u;
}
#define ls t[u].ch[0]
#define rs t[u].ch[1]
void rever(int u){
	swap(ls,rs);
	t[u].tag^=1;
}
void pushdown(int u){
	if(t[u].tag){
		rever(ls);
		rever(rs);
		t[u].tag^=1;
	}
}
void pushup(int u){
	t[u].siz=t[ls].siz+t[rs].siz+t[u].siz2+1;
}
void rotate(int u){
	int Y=t[u].fa;
	int R=t[Y].fa;
	int Yson=get_son(u);
	int Rson=get_son(Y);
	int B=t[u].ch[!Yson];
	if(isroot(Y))t[R].ch[Rson]=u;
	t[u].fa=R;
	t[Y].fa=u;
	t[u].ch[!Yson]=Y;
	t[B].fa=Y;
	t[Y].ch[Yson]=B;
	pushup(Y);
	pushup(u);
}
int top=0,sta[N];
void splay(int u){
	int x=u;
	sta[++top]=x;
	while(isroot(x)){
		x=t[x].fa;
		sta[++top]=x;
	}
	while(top){
		pushdown(sta[top]);
		top--;
	}
	while(isroot(u)){
		int fa=t[u].fa;
		if(isroot(fa)){
			if(get_son(u)==get_son(fa))rotate(fa);
			else rotate(u);
		}
		rotate(u);
	}
}
void access(int u){
	for(int x=0;u;x=u,u=t[u].fa){
		splay(u);
		t[u].siz2+=t[t[u].ch[1]].siz-t[x].siz;
		t[u].ch[1]=x;
		pushup(u);
	}
}
void makeroot(int u){
	access(u);
	splay(u);
	rever(u);
}
void link(int x,int y){
	makeroot(x);
	makeroot(y);
	t[x].fa=y;
	t[y].siz2+=t[x].siz;
	pushup(y);
}
void cut(int x,int y){
	makeroot(x);
	access(y);
	splay(x);
	t[x].ch[1]=t[y].fa=0;	
	pushup(y);pushup(x);
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)t[i].siz=1;
	for(int i=1;i<=q;i++){
		char op;
		int x,y;
		cin>>op>>x>>y;
		if(op=='A'){
			link(x,y);
		}
		else{
			cut(x,y);
			makeroot(x);
			int ans1=t[x].siz;
			makeroot(y);
			int ans2=t[y].siz;
			link(x,y);
			cout<<ans1*ans2<<"\n";
		}
	}
}

维护树上染色联通块

特殊题型