LCT

发表于 | 分类于

动态树

—维护树的连通性的强力武器

功能

LCT(link-cut tree)支持树（森林）的link,cnt,换根(makeroot)等等操作，而且也能维护树上的权值。

实现比较神奇。每个点都有一个preferred son。但是这不一定是由子树大小来决定的。他们两个之间的边称为preferred edge。

动态树使用更加灵活的Splay来实现。对于一段连续的边，即一条由preferred edge组成的preferred path上的点，保存在同一颗Splay中。Splay按深度关系来维护这些点。同时根节点的父亲指向当前Splay中深度最浅的点在原树中的父亲，但是这个父亲的儿子并不是这个点，所以可以依据这个来判断是不是根。

由以下核心操作来实现

Access x 将x到根节点的路径变为preferred path

Split x y 将x,y变到同一个Splay中

代码

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+1e3+7;
int n,m,fa[N],son[N][2],size[N],key[N],sum[N],mx[N],tag[N],rev[N];
bool isroot(int x)
{
	return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
void add(int x,int v)
{
	key[x]+=v;
	sum[x]+=v*size[x];
	mx[x]+=v;
	tag[x]+=v;
}
void pushup(int x)
{
	sum[x]=sum[son[x][0]]+sum[son[x][1]]+key[x];
	mx[x]=max(max(mx[son[x][0]],mx[son[x][1]]),key[x]);
	size[x]=size[son[x][0]]+size[son[x][1]]+1;
}
void pushdown(int x)
{
	if(rev[x])
	{
		rev[x]^=1;
		rev[son[x][0]]^=1;
		rev[son[x][1]]^=1;
		swap(son[x][0],son[x][1]);
	}
	if(tag[x])
	{
		add(son[x][0],tag[x]);
		add(son[x][1],tag[x]);
		tag[x]=0;
	}
}
void rotate(int x)
{
	pushdown(fa[x]),pushdown(x);
	int y=fa[x],z=fa[y],t=son[y][0]==x;
	if(!isroot(y))
		son[z][son[z][1]==y]=x;
	fa[x]=z;
	son[y][!t]=son[x][t];
	fa[son[y][!t]]=y;
	son[x][t]=y;
	fa[y]=x;
	pushup(y);
	pushup(x);
}
void splay(int x)
{
	pushdown(x);
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y];
		if(!isroot(y))
		{
			if((son[x][0]==x)^(son[z][0]==y))
				rotate(x);
			else
				rotate(y);
		}
		rotate(x);
	}
}
void access(int x)
{
	for(int y=0;x;y=x,x=fa[x])
	{
		splay(x);
		son[x][1]=y;
		pushup(x);
	}
}
void makeroot(int x)
{
	access(x);
	splay(x);
	rev[x]^=1;
}
void split(int x,int y)
{
	makeroot(x);
	access(y);
	splay(x);
}
void link(int x,int y)
{
	makeroot(x);
	fa[x]=y;
}
void cut(int x,int y)
{
	split(x,y);
	son[x][1]=fa[y]=0;
}
int find(int x)
{
	access(x);
	splay(x);
	while(son[x][0]) 
		x=son[x][0];
	return x;
}
int main()
{
	mx[0]=-0x7fffffff;
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)
	  scanf("%d",&x),size[i]=1,add(i,x),tag[i]=0;
	for(int i=1,opt,x,y,z;i<=m;i++)
	{
		scanf("%d%d%d",&opt,&x,&y);
		if(opt==1) link(x,y);
		else if(opt==2) cut(x,y);
		else if(opt==3) splay(x),key[x]=y,pushup(x); //更改x的权值为y
		else if(opt==4) split(x,y),printf("%d\n",mx[x]); //求x到y路径上的最大值
		else if(opt==5) split(x,y),printf("%d\n",sum[x]); //求x到y路径上的和
		else if(opt==6) printf("%d\n",find(x)==find(y));  //判断x和y是否连通
		else scanf("%d",&z),split(x,y),add(x,z);  //将x到y路径上加z
	}
}

每个操作的实现都比较清晰明了。

例题

弹飞绵羊(bzoj 2002)

只包括简单地连边操作。对于每一个会跳飞的结点，我们可以设置一个结点，即n+1来连边。事实上一个点能跳的步数就是将这棵树反过来之后(makeroot)在Splay上的左儿子的size，即深度比其浅的点。

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
	#include<cstdio>
	#include<iostream>
	using namespace std;
	
	const int N=2e5+1e3+7;
	
	int son[N][2],n,m,fa[N],rev[N],size[N],k[N];
	
	int isroot(int x)
	{
		return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
	}
	
	void pushup(int x)
	{
		size[x]=size[son[x][0]]+size[son[x][1]]+1;
	}
	
	void pushdown(int x)
	{
		if(rev[x])
		{
			rev[x]^=1;
			rev[son[x][0]]^=1;
			rev[son[x][1]]^=1;
			swap(son[x][0],son[x][1]);
		}
	}
	
	void rotate(int x)
	{
		pushdown(fa[x]),pushdown(x);
		int y=fa[x],z=fa[y],t=son[y][0]==x;
		if(!isroot(y))
			son[z][son[z][1]==y]=x;
		fa[x]=z;
		son[y][!t]=son[x][t];
		fa[son[y][!t]]=y;
		son[x][t]=y;
		fa[y]=x;
		pushup(y);
		pushup(x);
	}
	
	void splay(int x)
	{
		pushdown(x);
		while(!isroot(x))
		{
			int y=fa[x],z=fa[y];
			if(!isroot(y))
			{
				if(son[y][0]==x^son[z][0]==y)
					rotate(x);
				else
					rotate(y);
			}
			rotate(x);
		}
	}
	
	void access(int x)
	{
		for(int y=0;x;y=x,x=fa[x])
		{
			splay(x);
			son[x][1]=y;
			pushup(x);
		}
	}
	
	void makeroot(int x)
	{
		access(x);
		splay(x);
		rev[x]^=1;
	}
	
	void split(int x,int y)
	{
		makeroot(x);
		access(y);
		splay(x);
	}
	
	void link(int x,int y)
	{
		makeroot(x);
		fa[x]=y;
	}
	
	void cut(int x,int y)
	{
		split(x,y);
		son[x][1]=fa[y]=0;
	}
	
	int main()
	{
		freopen("bzoj_2002.in","r",stdin);
		freopen("bzoj_2002.out","w",stdout);
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&k[i]);
			if(k[i]+i>=n+1)
				k[i]=n+1-i;
			link(i,i+k[i]);
			size[i]=1;
		}
		size[n+1]=1;
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			int op,x,val;
			scanf("%d%d",&op,&x);
			x++;
			if(op==1)
			{
				makeroot(n+1);
				access(x),splay(x);
				printf("%d\n",size[son[x][0]]);
			}
			else
			{
				scanf("%d",&val);
				cut(x,x+k[x]);
				k[x]=val;
				if(k[x]+x>=n+1)
					k[x]=n+1-x;
				link(x,x+k[x]);
			}
		}
	}
```    
### [洞穴勘测](http://www.lydsy.com/JudgeOnline/problem.php?id=2049)
这题就是最基础的link和cut还有find(判断一个点所在树的根)
```cpp	
    #include<cstdio>
	#include<iostream>
	using namespace std;
	
	const int N=2e5+1e3+7;
	
	int son[N][2],n,m,fa[N],rev[N],size[N],k[N];
	
	int isroot(int x)
	{
		return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
	}
	
	void pushup(int x)
	{
		size[x]=size[son[x][0]]+size[son[x][1]]+1;
	}
	
	void pushdown(int x)
	{
		if(rev[x])
		{
			rev[x]^=1;
			rev[son[x][0]]^=1;
			rev[son[x][1]]^=1;
			swap(son[x][0],son[x][1]);
		}
	}
	
	void rotate(int x)
	{
		pushdown(fa[x]),pushdown(x);
		int y=fa[x],z=fa[y],t=son[y][0]==x;
		if(!isroot(y))
			son[z][son[z][1]==y]=x;
		fa[x]=z;
		son[y][!t]=son[x][t];
		fa[son[y][!t]]=y;
		son[x][t]=y;
		fa[y]=x;
		pushup(y);
		pushup(x);
	}
	
	void splay(int x)
	{
		pushdown(x);
		while(!isroot(x))
		{
			int y=fa[x],z=fa[y];
			if(!isroot(y))
			{
				if(son[y][0]==x^son[z][0]==y)
					rotate(x);
				else
					rotate(y);
			}
			rotate(x);
		}
	}
	
	void access(int x)
	{
		for(int y=0;x;y=x,x=fa[x])
		{
			splay(x);
			son[x][1]=y;
			pushup(x);
		}
	}
	
	void makeroot(int x)
	{
		access(x);
		splay(x);
		rev[x]^=1;
	}
	
	void split(int x,int y)
	{
		makeroot(x);
		access(y);
		splay(x);
	}
	
	void link(int x,int y)
	{
		makeroot(x);
		fa[x]=y;
	}
	
	void cut(int x,int y)
	{
		split(x,y);
		son[x][1]=fa[y]=0;
	}
    int main(){
    //	freopen("sdoi2008_cave.in","r",stdin);
    //	freopen("sdoi2008_cave.out","w",stdout);
        scanf("%d%d",&m,&n);
        for (int i = 1;i <= n;i++){
            int x,y;
            scanf("%s",s);
            scanf("%d%d",&x,&y);
            if (s[0] == 'C')	link(x,y);
            else if (s[0] == 'D')	cut(x,y);
            else {
                if (find(x) == find(y))	printf("Yes\n");
                else printf("No\n");
            }
        }
        return 0;
    }

COGS动态树

这题是FoolMike大佬刚出的啊。这题需要一些奇怪的操作，维护子树大小的信息。但是普通的LCT不能搞啊。我们需要在树上再记录一个信息，即其非preferred son的子树大小，然后size去掉这个。这样的话，就可以在access的时候灵活地修改了

但是好像还有别的高级LCT可以解决这个问题啊

留一个tag

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
us1ing namespace std;
const int N=2e5+1e3+7;
int n,m,fa[N],son[N][2],size[N],key[N],rev[N],vir[N];
bool isroot(int x)
{
    return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
void pushup(int x)
{
    size[x]=vir[x]+size[son[x][0]]+size[son[x][1]]+1;
}
void pushdown(int x)
{
    if(rev[x])
    {
        rev[son[x][0]]^=1;
        rev[son[x][1]]^=1;
        swap(son[x][0],son[x][1]);
        rev[x]^=1;
    }
}
void rotate(int x)
{
    pushdown(fa[x]),pushdown(x);
    int y=fa[x],z=fa[y],t=(son[y][0]==x);
    if(!isroot(y))
        son[z][son[z][1]==y]=x;
    fa[x]=z;
    son[y][!t]=son[x][t];
    fa[son[y][!t]]=y;
    son[x][t]=y;
    fa[y]=x;
    pushup(y);
    pushup(x);
}
void splay(int x)
{
    pushdown(x);
    while(!isroot(x))
    {
        int y=fa[x],z=fa[y];
        if(!isroot(y))
        {
            if((son[y][0]==x)^(son[z][0]==y))
                rotate(x);
            else
                rotate(y);
        }
        rotate(x);
    }
}
void access(int x)
{
    for(int y=0;x;y=x,x=fa[x])
    {
        splay(x);
        vir[x]-=size[y];
        vir[x]+=size[son[x][1]];
        son[x][1]=y;
        pushup(x);
    }
}
void makeroot(int x)
{
    access(x);
    splay(x);
    rev[x]^=1;
}
void link(int x,int y)
{
    makeroot(y);
    fa[y]=x;
    vir[x]+=size[y];
}
int find(int x)
{
    access(x);
    splay(x);
    while(son[x][0]) 
        x=son[x][0];
    return x;
}
int main()
{
    freopen("dynamic_tree.in","r",stdin);
    freopen("dynamic_tree.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
      size[i]=1;
    for(int i=1;i<=m;i++)
    {
        int u,opt;
        scanf("%d%d",&opt,&u);
        if(opt==1)
            makeroot(u);
        if(opt==2)
        {
            access(u);
            printf("%d\n",vir[u]+1); 
        }
        if(opt==3)
        {
            int v;
            scanf("%d",&v);
            int k=find(u);
            link(u,v);
            makeroot(k);
        }
    }
}