Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

LCT(Link-Cut-Tree)

算法

发布于：Apr 30, 2022

更新于：Aug 15, 2024

次浏览

LCT维护一个森林，即把每个节点用splay维护，可以进行许多操作：

  • 查询、修改链上的信息

  • 随意指定原树的根（即换根）

  • 动态连边、删边

  • 合并两棵树、分离一棵树

  • 动态维护连通性

  • 等

主要性质

  1. 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。
  2. 每个节点仅包含于一个splay中。
  3. 边分为实边和虚边，实边记录 son 和 fa，包含在一个 splay 中。为了维护 splay 树形，虚边仅记录 fa。不过虚边是由 splay(根） 指向父亲的，不一定是原节点。

操作

access

access 操作是指将一个点到树根的路径打通，即把根节点和该节点搞到一个 splay 上。

我们从 x 向上爬。

  • 每次将所在节点 splay（转到 splay 的根节点）
  • 将该 splay 所指向的节点的儿子换为 splay 的根节点。
  • 更新信息。
  • 将操作点切换到父节点，重复操作直到节点的父亲是0。
1
2
3
4
5
void access(int x){
    for(int y=0;x;y=x,x=fa[x]){
        splay(x);son[x][1]=y;pushup(x);
	}
}

makert

makert 操作可以将一个节点变成整棵树的根。

  • 将该节点 access 。
  • 将该节点 splay 。
  • 将该节点打上子树翻转标记。

正确性为，access 操作后将该节点到原来的根的路径打通并成为一个 splay 后，整条路径的 dfs 序都会反转，而其他节点的 dfs 序都不会变。

1
2
inline void rev(const int &x){tag[x]^=1,swap(son[x][0],son[x][1]);}
void makert(int x){access(x),splay(x),rev(x);}

findrt

findrt 操作可以找到一个节点在其树内的根。

  • 将该节点 access。
  • 将该节点 splay。
  • 一直跳左儿子，则找到 dfs 序最小的节点，也就是根。
1
int findrt(int x){access(x),splay(x);while(son[x][0])x=son[x][0];splay(x);return x;}

注意，上面的代码中如果不在找到根后 splay 复杂度是假的。

link 操作将两个连通块进行连边。

  • 若要在连边之前判断两者是否已经联通，可以将一个节点变成根，查找另一个节点的根进行判断。
  • 一般连边是将一个节点变成另一个节点的虚儿子，也就是连虚边。这种方式适用于虚儿子贡献较为简单计算的情况。设这两个节点为 x 和 y，我们将 y makert ，将 x splay，然后将 y 的 fa 改成 x 即可。（如果要统计子树信息的话，将两个节点都改为根，然后连边时顺便统计字数贡献）
  • 当然也可以直接连成实边。
1
2
3
4
void link(int x,int y){
    makert(x);
    if(findrt(y)!=x) fa[x]=y;
}
1
2
3
4
5
inline void link(int x,int y){
    splay(x);fa[x]=y;
    access(y),splay(y);
    son[y][1]=x;pushup(y);
}

cut

cut 操作将两个点间进行删边。

  • 若要判断两个点原先是否有边相连，先将一个节点设成根然后判断连通性，再判断两点间的 dfs 序是否连续。
  • 然后直接将上面节点的儿子和下面节点的父亲设为 0 即可。别忘了更新信息。
1
2
3
4
inline void cut(int x,int y){
    makert(x);
    if(findrt(y)==x and fa[y]==x and !son[y][0]) rs=fa[y]=0,pushup(x);
}

模板

维护链上最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
struct LCT{
    #define ls son[x][0]
    #define rs son[x][1]
    int tag[maxm],fa[maxm],st[maxm],mx[maxm],id[maxm],son[maxm][2];
    inline bool notrt(int x){return son[fa[x]][0]==x or son[fa[x]][1]==x;}
    inline int getw(int x){return son[fa[x]][1]==x;}
    inline void rev(int x){if(x)swap(ls,rs),tag[x]^=1;}
    inline void pushup(int x){
        if(mx[ls]>mx[rs])mx[x]=mx[ls],id[x]=id[ls];
        else mx[x]=mx[rs],id[x]=id[rs];
        if(val[x]>mx[x])mx[x]=val[x],id[x]=x;
    }
    inline void pushdown(int x){if(tag[x])tag[x]=0,rev(ls),rev(rs);}
    inline void rotate(int x){
        int y=fa[x],z=fa[y],w=getw(x),s=son[x][!w];
        if(notrt(y))son[z][getw(y)]=x;
        son[x][!w]=y;son[y][w]=s;
        if(s)fa[s]=y;fa[x]=z,fa[y]=x;
        pushup(y);pushup(x);
    }
    inline void splay(int x){
        int y,top=1;
        for(y=x;notrt(st[++top]=y);y=fa[y]);
        while(top)pushdown(st[top--]);
        while(notrt(x)){
            y=fa[x];
            if(notrt(y)) rotate((getw(x)^getw(y))?x:y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x){
        for(int y=0;x;y=x,x=fa[x])
            splay(x),rs=y,pushup(x);
    }
    inline int findroot(int x){
        access(x),splay(x);
        while(ls)x=ls;
        splay(x);
        return x;
    }
    inline void makeroot(int x){access(x),splay(x),rev(x);}
    inline void split(int x,int y){makeroot(x);access(y),splay(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 and fa[y]==x and !son[y][0])
            fa[y]=rs=0,pushup(x);
    }
    #undef ls
    #undef rs
}L;

进阶

维护子树信息

LCT 可以维护子树信息，但是只能做到查询而做不到修改。简单来说，维护的方式就是每次给一个 splay 添加一个虚儿子的时候，需要多开一个数据结构记录虚儿子的贡献。然后在上传的时候考虑虚儿子即可。

P4219 [BJOI2014]大融合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=1e5+10;
	int n,m;
	struct LCT{
		#define ls son[x][0]
		#define rs son[x][1]
		int tag[maxn],son[maxn][2],fa[maxn],siz[maxn],siz2[maxn],st[maxn];
		inline bool getw(int x){return son[fa[x]][1]==x;}
		inline void rev(int x){if(x)tag[x]^=1,swap(ls,rs);}
		inline void pushup(int x){siz[x]=siz[ls]+siz[rs]+siz2[x]+1;}
		inline void pushdown(int x){if(tag[x])tag[x]=0,rev(ls),rev(rs);}
		inline bool notrt(int x){return son[fa[x]][0]==x or son[fa[x]][1]==x;}
		inline void rotate(int x){
			int y=fa[x],z=fa[y],w=getw(x),s=son[x][!w];
			if(notrt(y))son[z][getw(y)]=x;son[y][w]=s;son[x][!w]=y;
			if(s)fa[s]=y;fa[y]=x,fa[x]=z;
			pushup(y);
		}
		inline void splay(int x){
			int y;int top=0;
			for(y=x;notrt(st[top++]=y);y=fa[y]);
			while(top--)pushdown(st[top]);
			while(notrt(x)){
				y=fa[x];
				if(notrt(y)) rotate(getw(x)^getw(y)?x:y);
				rotate(x);
			}
			pushup(x);
		}
		inline void access(int x){for(int y=0;x;y=x,x=fa[x])splay(x),siz2[x]+=siz[rs]-siz[y],rs=y,pushup(x);}
		inline void makert(int x){access(x),splay(x),rev(x);}
		inline int findrt(int x){access(x),splay(x);while(ls)x=ls;splay(x);return x;}
		inline void split(int x,int y){makert(x);access(y),splay(y);}
		inline void link(int x,int y){makert(x);if(findrt(y)!=x)fa[x]=y,siz2[y]+=siz[x],splay(y);}
		inline void cut(int x,int y){
			makert(x);
			if(findrt(y)==x and fa[y]==x and !son[y][0]) rs=fa[y]=0,pushup(x);
		}
		#undef ls
		#undef rs
	}L;
	inline void work(){
		n=read(),m=read();
		int x,y;
		while(m--){
			char c=getchar();
			while(!isalpha(c))c=getchar();
			if(c=='A')L.link(read(),read());
			else L.split(x=read(),y=read()),printf("%lld\n",1ll*(L.siz2[x]+1)*(L.siz2[y]+1));
		}
	}
}
signed main(){
	star::work();
	return 0;
}

动态求LCA

LCT 本来就是动态的，如何求两个点的 LCA 呢？

将其中一个点 access ，然后将另外一个点 access ，并记录最后一次 splay 前找到的节点（即最后的代码中的y）

利用LCT的结构

LCT 是一种优秀的暴力，它的结构有时候可以帮我们做一些很强的题目（虽然一般都想不到这个模型）

P3703 [SDOI2017]树点涂色

思路：观察操作，有“将一个点到根节点的路径染成同一种新的颜色”，发现同一颜色的连通块都是一条链，那么我们很快想到 LCT 的模型。维护的答案是该节点到根的 splay 个数。那么我们在改变 access 的时候，即改变儿子虚实的时候，需要将虚儿子子树内所有节点的答案都增加，将实儿子子树内所有节点都减少，这个可以用线段树进行维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=1e5+10;
	int n,m;
	int dfn[maxn],dep[maxn],id[maxn],fa[maxn],son[maxn],siz[maxn],top[maxn];
	int ecnt,head[maxn],nxt[maxn<<1],to[maxn<<1];
	inline void addedge(int a,int b){
		to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;
		to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;
	}
	void dfs1(int x,int f){
		fa[x]=f,dep[x]=dep[f]+1,siz[x]=1;
		for(int u,i=head[x];i;i=nxt[i]) if((u=to[i])!=f){
			dfs1(u,x);
			siz[x]+=siz[u];
			if(siz[u]>siz[son[x]]) son[x]=u;
		}
	}
	void dfs2(int x,int topf){
		top[x]=topf;dfn[x]=++dfn[0],id[dfn[0]]=x;
		if(!son[x])return;
		dfs2(son[x],topf);
		for(int u,i=head[x];i;i=nxt[i]) if((u=to[i])!=fa[x] and u!=son[x]) dfs2(u,u);
	}
	inline int LCA(int x,int y){
		while(top[x]!=top[y]) if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
		else y=fa[top[y]];
		return dep[x]<dep[y]?x:y;
	}
	struct SegmentTree{
		#define ls (ro<<1)
		#define rs (ro<<1|1)
		#define mid ((l+r)>>1)
		int mx[maxn<<2],tag[maxn<<2];
		inline void pushup(const int &ro){mx[ro]=max(mx[ls],mx[rs]);}
		inline void pushdown(const int &ro){tag[ls]+=tag[ro],tag[rs]+=tag[ro];mx[ls]+=tag[ro],mx[rs]+=tag[ro];tag[ro]=0;}
		void build(const int &ro=1,const int &l=1,const int &r=n){
			if(l==r)return mx[ro]=dep[id[l]],tag[ro]=0,void();
			build(ls,l,mid),build(rs,mid+1,r);
			pushup(ro);
		}
		void update(const int &x,const int &y,const int &k,const int &ro=1,const int &l=1,const int &r=n){
			if(x==l and y==r) return tag[ro]+=k,mx[ro]+=k,void();
			if(tag[ro])pushdown(ro);
			if(y<=mid) update(x,y,k,ls,l,mid);
			else if(x>mid) update(x,y,k,rs,mid+1,r);
			else update(x,mid,k,ls,l,mid),update(mid+1,y,k,rs,mid+1,r);
			pushup(ro);
		}
		int query(const int &x,const int &y,const int &ro=1,const int &l=1,const int &r=n){
			if(x==l and y==r)return mx[ro];
			if(tag[ro])pushdown(ro);
			if(y<=mid) return query(x,y,ls,l,mid);
			if(x>mid) return query(x,y,rs,mid+1,r);
			return max(query(x,mid,ls,l,mid),query(mid+1,y,rs,mid+1,r));
		}
		#undef ls
		#undef rs
		#undef mid
	}T;
	struct LCT{
		#define ls son[x][0]
		#define rs son[x][1]
		int son[maxn][2],fa[maxn];
		inline bool notrt(int x){return son[fa[x]][0]==x or son[fa[x]][1]==x;}
		inline int getw(int x){return son[fa[x]][1]==x;}
		inline void rotate(int x){
			int y=fa[x],z=fa[y],w=getw(x),s=son[x][!w];
			if(notrt(y)) son[z][getw(y)]=x;son[y][w]=s,son[x][!w]=y;
			if(s) fa[s]=y;fa[y]=x,fa[x]=z;
		}
		inline void splay(int x){
			while(notrt(x)){
				int y=fa[x];
				if(notrt(y))rotate(getw(x)^getw(y)?x:y);
				rotate(x);
			}
		}
		inline int findrt(int x){while(ls)x=ls;return x;}
		inline void access(int x){
			for(int u,y=0;x;y=x,x=fa[x]){
				splay(x);
				if(rs) u=findrt(rs),T.update(dfn[u],dfn[u]+siz[u]-1,1);
				if(rs=y) u=findrt(rs),T.update(dfn[u],dfn[u]+siz[u]-1,-1);
			}
		}
		#undef ls
		#undef rs
	}S;
	inline void work(){
		n=read(),m=read();
		for(int i=1;i<n;i++) addedge(read(),read());
		dfs1(1,0);dfs2(1,1);
		for(int i=1;i<=n;i++) S.fa[i]=fa[i];
		T.build();
		while(m--)
		switch(read()){
			case 1:S.access(read());break;
			case 2:{
				int x=read(),y=read(),lca=LCA(x,y);
				printf("%d\n",T.query(dfn[x],dfn[x])+T.query(dfn[y],dfn[y])-2*T.query(dfn[lca],dfn[lca])+1);
				break;
			}
			case 3:{
				int x=read();
				printf("%d\n",T.query(dfn[x],dfn[x]+siz[x]-1));
			}
		}
	}
}
signed main(){
	star::work();
	return 0;
}

P6292 区间本质不同子串个数也用到了这个 trick。

更多trick

待耕。

更新于：Aug 15, 2024

博客园

OI

图论

给小狼留言