This is not the end.

0%

Link Cut Tree(LCT)

Posted on

LCT

前言

LCT用来维护的是森林。它可以支持加边（link)、删边（cut）、链信息修改和查询、子树信息查询。

LCT长啥样

首先我们对这些树进行实链剖分。我们对树中的每一条实链都用一棵splay维护。splay维护的是实链上的点按照深度从小到大排序后得到的序列。一个点在splay上的前驱和后继是它在实链和它相邻的点。splay中每个点的编号和这个点在树中的编号是相同的。特别的，一条实链的splay的根节点的父亲，是成这条实链的最浅点在树上的父亲。

基本操作

isroot(x)

这个函数用来判断x这个点是不是它所属的splay的根。

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

splay(x)

我们用这个函数把x转到x所属的splay的根节点。

注意rotate里面关于x的祖先的判断，要调用isroot(f)，并且要在修改f的父亲之前。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void rotate(int x) {
	int f=fa[x],ff=fa[f],d=get(x);
	fa[x]=ff; if(!isroot(f)) ch[ff][ch[ff][1]==f]=x;
	fa[ch[x][d^1]]=f,ch[f][d]=ch[x][d^1];
	fa[f]=x,ch[x][d^1]=f; push_up(f),push_up(x);
}
inline void PD(int x) {
	static int stk[N],top;
	stk[top=1]=x;
	while(!isroot(x)) stk[++top]=fa[x],x=fa[x];
	while(top) push_down(stk[top--]);
}
void splay(int x) {
	PD(x);
	for(int f=fa[x];!isroot(x);rotate(x),f=fa[x])
		if(!isroot(f)) rotate(get(x)==get(f)?f:x);
}

要注意，如果x自己就是根节点，那么将不会执行到rotate语句，如果把push_down写在rotate里面，标记的下放就会有一些问题。

access(x)

利用这个函数我们让x和这棵树的根在同一条实链上，并且恰好是实链的两端。

首先我们把x转到它自己所属的splay的根部，此时它的右儿子部分是它在实链中比它深的点，应该和它断开。考虑x上方的实链，我们应该对fa[x]进行类似的操作（splay到根然后把右儿子和它断开)，并且把x接在它的右儿子的位置。然后对fa[fa[x]]也进行这样的操作，直到x和根在同一条实链上。

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

makeroot(x)

利用这个函数我们把x变成全树的根。

首先access(x)，然后我们要让x成为实链上的最浅点。注意到此时x恰好是实链上的最深点，那么我们直接对这个splay进行区间翻转操作就可以达到目的。

1
void makeroot(int x) { access(x),splay(x),Swap(x); }

把x置为根，把x所在的splay的根的父亲设置成y就可以了。

1
2
3
void link(int x,int y) {
	makeroot(x),splay(x),fa[x]=y;
}

cut(x,y)

把x设为根，然后access(y)，在splay上把两个点断开就可以了。

1
2
3
4
5
void cut(int x,int y) {
	makeroot(x),access(y),splay(y);
	fa[ch[y][0]]=0,ch[y][0]=0;
	push_up(y);
}

判断两个点之间是否有边，makeroot(x),access(y),splay(y)，然后判断ch[x][0] 是否为空。

findroot(x)

找出x这个点所在的树的根。

首先access(x)，然后找出x所在实链的最浅点。

操作

区间修改/查询

如果要修改/查询从x到y的链信息，先makeroot(x)，然后access(y)，此时我们需要的链恰好就是x，y所属的实链。转化成splay的修改和查询就可以了。

子树信息

我们对每一个点，记录一个vir[u]，表示它的所有虚儿子的子树信息的和。

我们在splay上维护这个点的splay子树内，所有的点及其虚子树的信息的和。

1
sum[u]=sum[ch[u][0]]+sum[ch[u][1]]+vir[u]+val[u];

只有轻重链切换的时候，我们需要考虑vir[u]的修改。

1
2
3
4
5
6
7
void access(int x) {
    for(int y=0;x;y=x,x=fa[x]) {
      	splay(x);
        if(ch[x][1]) vir[x]-=sum[ch[x][1]];
        if(y) vir[x]+=sum[y];
        ch[x][1]=y,push_up(x);
    }

求两个点的lca

首先access(x)，然后执行access(y)。注意到lca(x,y)就是我们在access(y)的过程中跳到最后一条实链上，我们跳到的那个点。

1
2
3
4
5
6
7
8
9
10
int access(int x) {
    int y;
    for(y=0;x;y=x,x=fa[x]) {
        splay(x),ch[x][1]=y,push_up(x);
    }
    return y;
}
int lca(int x,int y) {
    access(x); return access(y);
}

当然，操作是无穷多的，只要你脑洞足够大hhh

模板

tree II

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x)
{
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=1e5+10,mod=51061;
int ch[N][2],fa[N],n;
int add[N],mul[N],rev[N];
int sum[N],val[N],sz[N];
bool isroot(int x) { return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x; }
int get(int x) { return ch[fa[x]][1]==x; } 
void Add(int x,int ad,int mu) {
//	cout<<"add"<<x<<' '<<sz[x]<<':'<<ad<<' '<<mu<<endl;
	if(!x) return;
	sum[x]=sum[x]*(ll)mu%mod,add[x]=add[x]*(ll)mu%mod;
	val[x]=val[x]*(ll)mu%mod,mul[x]=mul[x]*(ll)mu%mod;
	sum[x]=sum[x]+sz[x]*(ll)ad,val[x]=(val[x]+ad)%mod,add[x]=(add[x]+ad)%mod;
}
void Swap(int x) { swap(ch[x][0],ch[x][1]),rev[x]^=1; }
void push_down(int x) {
	if(rev[x]) Swap(ch[x][0]),Swap(ch[x][1]),rev[x]=0;
	Add(ch[x][0],add[x],mul[x]),Add(ch[x][1],add[x],mul[x]);
	add[x]=0,mul[x]=1;
}
void push_up(int x) {
	sum[x]=(sum[ch[x][0]]+sum[ch[x][1]]+val[x])%mod;
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
}
void rotate(int x) {
	int f=fa[x],ff=fa[f],d=get(x);
	fa[x]=ff; if(!isroot(f)) ch[ff][ch[ff][1]==f]=x;
	fa[ch[x][d^1]]=f,ch[f][d]=ch[x][d^1];
	fa[f]=x,ch[x][d^1]=f; push_up(f),push_up(x);
}
inline void PD(int x) {
	static int stk[N],top;
	stk[top=1]=x;
	while(!isroot(x)) stk[++top]=fa[x],x=fa[x];
	while(top) push_down(stk[top--]);
}
void splay(int x) {
	PD(x);
	for(int f=fa[x];!isroot(x);rotate(x),f=fa[x])
		if(!isroot(f)) rotate(get(x)==get(f)?f:x);
}
void access(int x) {
	for(int y=0;x;y=x,x=fa[x])
		splay(x),ch[x][1]=y,push_up(x);
}
void makeroot(int x) { access(x),splay(x),Swap(x); }
void split(int x,int y) {
	makeroot(x),access(y),splay(y);
}
void link(int x,int y) {
	makeroot(x),splay(x),fa[x]=y;
}
void cut(int x,int y) {
	makeroot(x),access(y),splay(y);
	fa[ch[y][0]]=0,ch[y][0]=0;
	push_up(y);
}
int main() {
	int q,x,y,w,u,v; char opt[232];
	rd(n),rd(q);
	for(int i=1;i<=n;++i) mul[i]=1,val[i]=1,push_up(i);
	for(int i=1;i<n;++i) rd(x),rd(y),link(x,y);
	while(q--) {
		scanf("%s",opt);
		if(opt[0]=='+') {
			rd(x),rd(y),rd(w);
			split(x,y); Add(y,w,1);
		}
		else if(opt[0]=='-') {
			rd(x),rd(y),rd(u),rd(v);
			cut(x,y),link(u,v);
		}
		else if(opt[0]=='/') {
			rd(x),rd(y); split(x,y);
			printf("%d\n",sum[y]);
		}
		else {
			rd(x),rd(y),rd(w);
			split(x,y); Add(y,0,w);
		}
	}
	return 0;
}