CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » jxm2001 » lct
2020-2021:teams:legal_string:jxm2001:lct

这是本文档旧的修订版！

目录

动态树

算法简介

动态树简称 LCT ，是一种动态维护森林连通性、路径信息的数据结构，时间复杂度为 $O\left(n\log n\right)$

算法思想

LCT 将树上路径分为实链和虚链，类似重链剖分，每个非叶结点仅向他的一个儿子结点连实边，其余儿子连虚边。

每个实链用一棵 splay 保存，同一棵树的 splay 之间靠虚边连接，每个 splay 维护一个深度递增的结点序列。

每棵 splay 树的根结点的父结点(注意，不是原树的父结点)设为这个 splay 深度最小的结点的在原树中的父节点。

LCT 的核心操作为 $\text{access}(x)$。

$\text{access}(x)$ 的目的是将 $x$ 结点到根结点的路径变为一条实链，便于后续操作，方法很简单，不断向上修改父子关系即可。

我们还想得到两个非根结点的路径信息，我们可以先将其中一个结点变为根结点，再使用 $\text{access}$ 操作。

将一个结点变为根结点即为 $\text{makeroot}(x)$ 操作，方法为先 $\text{access}(x)$ ，再颠倒这条实链。

颠倒实链可以考虑 $\text{splay}(x)$ ，$x$ 是 splay 中深度最小的点，无右儿子。

因此交换 $x$ 左右儿子， $x$ 无左儿子，成为深度最大的点，最后打上懒标记即可。

考虑到 LCT 维护的是森林，为了判断连通性，我们还需要 $\text{findroot}(x)$ ，即得到结点 $x$ 所在原树的根结点。

方法为先 $\text{access}(x)$ ，便可以得到结点 $x$ 到根结点的路径。

考虑到原树的根结点为深度最小的点，我们只需要 $\text{splay}(x)$ ，然后从结点 $x$ 出发不断访问右节点即可，但要注意下放懒标记。

有了这些基本操作，便可以实现树上的连边、删边、两点间的路径信息维护等操作了。

代码模板

查看代码

查看代码 

struct Link_Cut_tree{
	int ch[MAXN][2],fa[MAXN],w[MAXN],s[MAXN];
	int Stack[MAXN],top;
	bool flip[MAXN];
	#define lch(k) ch[k][0]
	#define rch(k) ch[k][1]
	void push_up(int k){
		s[k]=s[lch(k)]^s[rch(k)]^w[k];//自定义
	}
	void push_flip(int k){
		swap(lch(k),rch(k));
		flip[k]^=1;
	}
	void push_down(int k){
		if(flip[k]){
			push_flip(lch(k));
			push_flip(rch(k));
			flip[k]=0;
		}
	}
	bool isroot(int k){
		return lch(fa[k])!=k&&rch(fa[k])!=k;
	}
	void rotate(int k){
		int pa=fa[k],ga=fa[pa],dir;
		dir=ch[pa][0]==k?0:1;
		if(!isroot(pa))ch[ga][ch[ga][0]==pa?0:1]=k;
		fa[k]=ga,fa[pa]=k;
		if(ch[k][dir^1])fa[ch[k][dir^1]]=pa;
		ch[pa][dir]=ch[k][dir^1],ch[k][dir^1]=pa;
		push_up(pa);
	}
	void splay(int k){
		Stack[top=1]=k;
		for(int i=k;!isroot(i);i=fa[i])Stack[++top]=fa[i];
		while(top)push_down(Stack[top--]);
		while(!isroot(k)){
			int pa=fa[k],ga=fa[pa];
			if(!isroot(pa))rotate((ch[pa][0]==k)^(ch[ga][0]==pa)?k:pa);
			rotate(k);
		}
		push_up(k);
	}
	void access(int k){
		for(int t=0;k;t=k,k=fa[k]){
			splay(k);
			ch[k][1]=t;
			push_up(k);
		}
	}
	void makeroot(int k){
		access(k);
		splay(k);
		push_flip(k);
	}
	int findroot(int k){
		access(k);splay(k);
		push_down(k);
		while(ch[k][0])push_down(k=ch[k][0]);
		splay(k);
		return k;
	}
	void split(int u,int v){
		makeroot(u);
		access(v);
		splay(v);
	}
	void link(int u,int v){
		makeroot(u);
		if(findroot(v)!=u)fa[u]=v;
	}
	void cut(int u,int v){
		split(u,v);
		if(ch[v][0]==u&&ch[u][1]==0){
			ch[v][0]=fa[u]=0;
			push_up(v);
		}
	}
	void change(int k,int v){
		access(k);splay(k);
		w[k]=v;
		push_up(k);
	}
};

代码练习

习题1

洛谷p3690

给定 $n$ 个点和权值，接下来 $m$ 个操作。

操作 $0$ ：询问 $x$ 到 $y$ 路径的权值的异或和，保证 $x$ 与 $y$ 已经连通。

操作 $1$ ：连接 $x$ 与 $y$ ，若 $x$ 与 $y$ 已经连通，则无视这个操作。

操作 $2$ ：删除 $x$ 与 $y$ 的连边，若 $x$ 与 $y$ 无连边，则无视这个操作。

操作 $3$ ：把结点 $x$ 的权值改为 $y$。

一道LCT裸题，直接上代码。

查看代码

查看代码 

const int MAXN=1e5+5;
struct Link_Cut_tree{
	int ch[MAXN][2],fa[MAXN],w[MAXN],s[MAXN];
	int Stack[MAXN],top;
	bool flip[MAXN];
	#define lch(k) ch[k][0]
	#define rch(k) ch[k][1]
	void push_up(int k){
		s[k]=s[lch(k)]^s[rch(k)]^w[k];
	}
	void push_flip(int k){
		swap(lch(k),rch(k));
		flip[k]^=1;
	}
	void push_down(int k){
		if(flip[k]){
			push_flip(lch(k));
			push_flip(rch(k));
			flip[k]=0;
		}
	}
	bool isroot(int k){
		return lch(fa[k])!=k&&rch(fa[k])!=k;
	}
	void rotate(int k){
		int pa=fa[k],ga=fa[pa],dir;
		dir=ch[pa][0]==k?0:1;
		if(!isroot(pa))ch[ga][ch[ga][0]==pa?0:1]=k;
		fa[k]=ga,fa[pa]=k;
		if(ch[k][dir^1])fa[ch[k][dir^1]]=pa;
		ch[pa][dir]=ch[k][dir^1],ch[k][dir^1]=pa;
		push_up(pa);
	}
	void splay(int k){
		Stack[top=1]=k;
		for(int i=k;!isroot(i);i=fa[i])Stack[++top]=fa[i];
		while(top)push_down(Stack[top--]);
		while(!isroot(k)){
			int pa=fa[k],ga=fa[pa];
			if(!isroot(pa))rotate((ch[pa][0]==k)^(ch[ga][0]==pa)?k:pa);
			rotate(k);
		}
		push_up(k);
	}
	void access(int k){
		for(int t=0;k;t=k,k=fa[k]){
			splay(k);
			ch[k][1]=t;
			push_up(k);
		}
	}
	void makeroot(int k){
		access(k);
		splay(k);
		push_flip(k);
	}
	int findroot(int k){
		access(k);splay(k);
		push_down(k);
		while(ch[k][0])push_down(k=ch[k][0]);
		splay(k);
		return k;
	}
	void split(int u,int v){
		makeroot(u);
		access(v);
		splay(v);
	}
	void link(int u,int v){
		makeroot(u);
		if(findroot(v)!=u)fa[u]=v;
	}
	void cut(int u,int v){
		split(u,v);
		if(ch[v][0]==u&&ch[u][1]==0){
			ch[v][0]=fa[u]=0;
			push_up(v);
		}
	}
	void change(int k,int v){
		access(k);splay(k);
		w[k]=v;
		push_up(k);
	}
}LCT;
int main()
{
	int n=read_int(),m=read_int(),opt,u,v;
	_rep(i,1,n)
	LCT.w[i]=LCT.s[i]=read_int();
	_rep(i,1,m){
		opt=read_int(),u=read_int(),v=read_int();
		if(opt==0){
			LCT.split(u,v);
			enter(LCT.s[v]);
		}
		else if(opt==1)
		LCT.link(u,v);
		else if(opt==2)
		LCT.cut(u,v);
		else
		LCT.change(u,v);
	}
	return 0;
}

习题2

洛谷p1501

给定一棵 $n$ 个结点的树，每个结点初始权值为 $1$ ，接下来 $q$ 个操作

操作 $1$ ：将 $u$ 到 $v$ 路径上所有点权值加上 $c$

操作 $2$ ：删除 $u_1$ 与 $v_1$ 的连边，添加 $u_2$ 与 $v_2$ 的连边，保证操作后仍然是一棵树

操作 $3$ ：将 $u$ 到 $v$ 路径上所有点权值乘上 $c$

操作 $4$ ：查询 $u$ 到 $v$ 路径上权值和

一道简单LCT练手题，直接上代码

查看代码

查看代码 

const int MAXN=1e5+5,mod=51061;
struct Link_Cut_tree{
	int ch[MAXN][2],fa[MAXN],sz[MAXN];
	LL w[MAXN],s[MAXN],mul_tag[MAXN],add_tag[MAXN];
	int Stack[MAXN],top;
	bool flip[MAXN];
	void push_up(int id){
		s[id]=(s[ch[id][0]]+s[ch[id][1]]+w[id])%mod;
		sz[id]=sz[ch[id][0]]+sz[ch[id][1]]+1;
	}
	void push_add(int id,int v){
		s[id]=(s[id]+1LL*v*sz[id])%mod;
		w[id]=(w[id]+v)%mod;
		add_tag[id]=(add_tag[id]+v)%mod;
	}
	void push_mul(int id,int v){
		s[id]=s[id]*v%mod;
		w[id]=w[id]*v%mod;
		add_tag[id]=add_tag[id]*v%mod;
		mul_tag[id]=mul_tag[id]*v%mod;
	}
	void push_down(int id){
		if(flip[id]){
			swap(ch[id][0],ch[id][1]);
			flip[ch[id][0]]^=1;
			flip[ch[id][1]]^=1;
			flip[id]=0;
		}
		if(mul_tag[id]!=1){
			push_mul(ch[id][0],mul_tag[id]);
			push_mul(ch[id][1],mul_tag[id]);
			mul_tag[id]=1;
		}
		if(add_tag[id]){
			push_add(ch[id][0],add_tag[id]);
			push_add(ch[id][1],add_tag[id]);
			add_tag[id]=0;
		}
	}
	bool isroot(int id){return ch[fa[id]][0]!=id&&ch[fa[id]][1]!=id;}
	void rotate(int id){
		int pa=fa[id],ga=fa[pa],dir;
		dir=ch[pa][0]==id?0:1;
		if(!isroot(pa))ch[ga][ch[ga][0]==pa?0:1]=id;
		fa[id]=ga,fa[pa]=id,fa[ch[id][dir^1]]=pa;
		ch[pa][dir]=ch[id][dir^1],ch[id][dir^1]=pa;
		push_up(pa);push_up(id);
	}
	void splay(int id){
		Stack[top=1]=id;
		for(int i=id;!isroot(i);i=fa[i])Stack[++top]=fa[i];
		while(top)push_down(Stack[top--]);
		while(!isroot(id)){
			int pa=fa[id],ga=fa[pa];
			if(!isroot(pa))rotate((ch[pa][0]==id)^(ch[ga][0]==pa)?id:pa);
			rotate(id);
		}
	}
	void access(int id){
		for(int t=0;id;t=id,id=fa[id]){
			splay(id);
			ch[id][1]=t;
			push_up(id);
		}
	}
	void makeroot(int id){access(id);splay(id);flip[id]^=1;}
	int findroot(int id){
		access(id);splay(id);
		push_down(id);
		while(ch[id][0])push_down(id=ch[id][0]);
		return id;
	}
	void split(int u,int v){makeroot(u);access(v);splay(v);}
	void link(int u,int v){
		if(findroot(u)!=findroot(v)){
			makeroot(u);
			fa[u]=v;
		}
	}
	void cut(int u,int v){
		split(u,v);
		if(ch[v][0]==u&&ch[u][1]==0){
			ch[v][0]=fa[u]=0;
			push_up(v);
		}
	}
	void path_add(int u,int v,int val){
		split(u,v);
		push_add(v,val);
	}
	void path_mul(int u,int v,int val){
		split(u,v);
		push_mul(v,val);
	}
	int path_query(int u,int v){
		split(u,v);
		return s[v];
	}
}LCT;
int main()
{
	int n=read_int(),q=read_int(),u,v,c;
	_rep(i,1,n)
	LCT.w[i]=LCT.s[i]=LCT.sz[i]=1;
	_for(i,1,n){
		u=read_int(),v=read_int();
		LCT.link(u,v);
	}
	char opt;
	while(q--){
		opt=get_char();
		if(opt=='+'){
			u=read_int(),v=read_int(),c=read_int();
			LCT.path_add(u,v,c%mod);
		}
		else if(opt=='-'){
			u=read_int(),v=read_int();
			LCT.cut(u,v);
			u=read_int(),v=read_int();
			LCT.link(u,v);
		}
		else if(opt=='*'){
			u=read_int(),v=read_int(),c=read_int();
			LCT.path_mul(u,v,c%mod);
		}
		else{
			u=read_int(),v=read_int();
			enter(LCT.path_query(u,v));
		}
	}
	return 0;
}
2020-2021/teams/legal_string/jxm2001/lct.1625298861.txt.gz · 最后更改: 2021/07/03 15:54 由 jxm2001

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3