LinkCutTree动态树 学习笔记 [数据结构]

upd in 2019.1.8

真是震惊极了……我打了这么久的板子(包括网上某些LCT讲解中的代码)竟然复杂度是假的!!!

因为 splay 的复杂度是均摊的,每一次从根遍历了一条链就要将链尾 splay 上去(例如,如果当前的 splay 树形是一条长为 $n$ 递增的链->最大点为根,$m$ 次查询,每次查询第一个,如果不这样复杂度就变成 $O(mn)$ 了),才能保证复杂度均摊 $O(log n)$

所以,在 $findroot$ 后,应当将最后的 $x$ splay 到根。

别忘了修改一下 $cut(x,y)$ 的部分,要先判完 $findroot(x)==findroot(y)$ 再 $split(x,y)$ ,否则树形会被修改。

模板的代码是修改过的了,魔法森林的就不改了(以作对比)

顺便献上发现原因 uoj274 [清华集训2016]温暖会指引我们前行
修改前

修改后

(不要在意第 $20$ 个点的时间……)

写在前面

最近一直在补之前欠了好久的锅,像后缀自动机啊什么的,总算轮到 LCT 了,感觉也挺对不起的,学了这么久的 OI 了现在才学会这个……

但毕竟这个学习笔记主要还是给自己复习这个算法(老是忘)的时候看的,也就不讲的那么清楚了反正写这篇博客的时候我还是会的

概述

LCT实际是实链剖分,就是只有一个其中儿子的边的实边,其他的都是虚边,但是因为虚实可以动态变化,所以要用 splay 维护。

每一棵 splay 维护的是一条实链的信息,构成一个 splay 森林(原来的其实也是一个森林)。其中满足:
1、splay 按照深度为关键字对原树上节点排序,中序遍历 splay 树得到的是该实链的深度严格递增的排列。
2、每个节点在且仅在一棵 splay 中
3、父亲只认实儿子,儿子认父亲。(所以当一个点是它所在的实链的根的条件就是他的父亲没有他这个儿子)

因为原树是没有根的,所以本身也没有深度这一说,但是 LCT 中要指定一个根才行(然后就有了换根的操作)

可以资瓷:
1、查询、修改链上的信息 (子树不行!!!)
2、指定原树上一个点作为根(就是上面说的换根)
3、连边、删边、动态维护连通性
4、挖坑留给以后见到的神奇用法

操作

$isroot(x)$

判断 $x$ 是不是它所在实链的根 -> $x$ 不是 $fa[x]$ 的任意一个儿子。

$access(x)$

这个操作很重要所以要大一点
打通 $x$ 到 $x$ 的路径为新的实链,即 $x$ 到 $x$ 的路径上的点维护在一棵 splay 中(没有图,所以只能感性理解)

方法:

1、将 $x$ splay 到所在实链的根,断开他的右子树 (深度比他大的点就不认了)

2、再看 $fa[x]$ 这个点,同样把它转到根,将刚刚的 $x$ 所在实链接在右子树上。

3、将 $x$ 变成 $fa[x]$,反复进行操作2直到 $fa[x]$ 不存在

1
2
3
4
5
inline void access(int x)
{
for(int tmp=0;x;tmp=x,x=fa[x])
splay(x),son[x][1]=tmp,update(x);
}

$makeroot(x)$

将 $x$ 作为原树的根,会修改的就是 splay 上按照深度的遍历顺序,因为 $access(x)$ 后 $x$ 一定是所在实链上深度最大的点,当 $x$ splay 到根时,是不会有右子树的,直接 $reverse$ 左右子树就达到了反转序列的效果了。

所以要打一个 $rev$ 的 $tag$ (和系列的 $pushdown$ 操作)

1
2
3
4
5
inline void reverse(const int &root) {rev[root]^=1,swap(ls,rs);}
inline void makeroot(const int root)
{
access(root),splay(root),reverse(root);
}

因为有了 $tag$ ,splay的时候就要注意 $pushdown$ 避免转错了。先将 $x$ 到 $root$ 的路径上点从上到小 $pushdown$ 完再 splay 吧。

$findroot(x)$

找到 $x$ 所在原树上的根,用于判断连通性。
方法:$access(x)$ 后 $x$ 所在 $splay$ 中深度最小的点(序列最左)的便是根了,再将 $x$ splay 到根,一路找左儿子便能找到根了。

1
2
3
4
5
6
inline int findroot(int root)
{
access(root),splay(root);
while(ls) pushdown(ls),root=ls;
return root;
}

upd:某位神仙告诉我splay了就不用pushdown了(好像很有道理)OrzOrz

$split(x,y)$

因为经常要求的是两点之间路径的情况,光是一个点到根是不够的,所以就有了 $split(x,y)$ 用于将 $x$ 的 $y$ 路径上的点放在一个 splay 中方便查询。
方法:将 $x$ 变成根以后,$access(y)$ 得到的便是 上述的 splay 了,此时再将 $y$ 转到根,便可以直接通过 $y$ 得到整个 splay (这条路径) 的所有信息了。

1
2
3
4
inline void split(const int x,const int y)
{
makeroot(x),access(y),splay(y);
}

将 $x$ 变成根以后,将 $X$ 的父亲置成 $y$ 便是连边 $x$、$y$ 了。别忘了判断当前的 $y$ 是不是已经在 $x$ 所在的树中了。

1
2
3
4
5
inline void link(const int x,const int y)
{
makeroot(x);
if(findroot(y)!=x) fa[x]=y;
}

$cut(x,y)$

如果保证存在边 $(x,y)$ 的话,$split(x,y)$ 后 $y$ 为根,$x$ 必为 $y$ 的左儿子(深度比 $y$ 小一),直接 $fa[x]=son[y][0]=0$断掉就行。

但是当不保证时需要满足:
1> $x$ 和 $y$ 在同一棵树中
2> $split(x,y)$ 后 $son[y][0]==x$
3> $split(x,y)$ 后 $x$ 没有右子树(因为 $x$ 的后继只应该是 $y$)

三个条件缺一不可

1
2
3
4
5
6
7
inline void cut(const int x,const int y)
{
split(x,y);
if(findroot(x)!=findroot(y)||son[y][0]!=x||son[x][1]) return;
fa[x]=son[y][0]=0;
update(y);
}

若还有别的操作待补

例题

洛咕
就是上面说的那些操作啦,splay 维护一下链 xor 和

代码

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
#include<bits/stdc++.h>
using namespace std;

namespace TYC
{
const int N=3e5+10;

inline int read()
{
int x=0,f=0;char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}

inline void write(int x)
{
int len=0;static int bask[50];
do bask[++len]=x%10,x/=10; while(x);
for(;len;len--) putchar('0'+bask[len]);
putchar('\n');
}

int val[N];

namespace LinkCutTree
{
int son[N][2],fa[N],sum[N],rev[N];

#define ls son[root][0]
#define rs son[root][1]

inline int dir(const int &root) {return son[fa[root]][1]==root;}
inline bool isroot(const int &root) {return son[fa[root]][0]!=root&&son[fa[root]][1]!=root;}
inline void update(const int &root) {sum[root]=sum[ls]^sum[rs]^val[root];}
inline void reverse(const int &root) {rev[root]^=1,swap(ls,rs);}
inline void pushdown(const int &root)
{
if(rev[root]) return;
if(ls) reverse(ls);
if(rs) reverse(rs);
rev[root]=1;
}

inline void rotate(const int &root)
{
int f=fa[root],d=dir(root);
if(!isroot(f)) son[fa[f]][dir(f)]=root;
fa[root]=fa[f];
fa[son[root][d^1]]=f;
son[f][d]=son[root][d^1];
son[root][d^1]=f,fa[f]=root;
update(f),update(root);
}
inline void splay(const int &root)
{
static int tot,list[N];
list[tot=1]=root;
for(int x=root;!isroot(x);x=fa[x]) list[++tot]=fa[x];
for(int i=tot;i;i--) pushdown(list[i]);
for(;!isroot(root);rotate(root))
if(!isroot(fa[root]))
rotate(dir(fa[root])^dir(root)?root:fa[root]);
}

inline void access(int root)
{
for(int tmp=0;root;tmp=root,root=fa[root])
splay(root),son[root][1]=tmp,update(root);
}

inline void makeroot(const int root)
{
access(root),splay(root),reverse(root);
}

inline void split(const int x,const int y)
{
makeroot(x);
access(y);
splay(y);
}

inline int findroot(int root)
{
access(root),splay(root);
while(ls) pushdown(ls),root=ls;
splay(root); //保证复杂度!!!
return root;
}

inline void link(const int x,const int y)
{
makeroot(x);
if(findroot(y)!=x) fa[x]=y;
}

inline void cut(const int x,const int y)
{
if(findroot(x)!=findroot(y)) return;
split(x,y);
if(son[y][0]!=x||son[x][1]) return;
fa[x]=son[y][0]=0;
update(y);
}
}

void work()
{
int n=read(),m=read();
for(int i=1;i<=n;i++) val[i]=read();
using namespace LinkCutTree;
while(m--)
{
int op=read(),x=read(),y=read();
switch(op)
{
case 0: split(x,y),write(sum[y]);break;
case 1: link(x,y);break;
case 2: cut(x,y);break;
case 3: val[x]=y,splay(x);
}
}
}
}

int main()
{
TYC::work();
return 0;
}

后来都把 root 打成 x 了,四个字母看着好长

二、bzoj3669 [Noi2014]魔法森林

洛咕2387 bzoj3669

先按照 $a$ 排序,然后对于边 $edge(u,v)$ 判断:
当 $u$,$v$ 没有连通时,加上 $edge$;否则,找到连通 $u$,$v$ 的边中 $b$ 最大的边 $t$,如果 $b(t) > b(edge)$,用 $edge$ 替换 $t$。(删掉 $t$ 加上 $edge$)

每次判断 $1$ 是否已经连通 $n$,若已连通,更新
$ans=min(ans,a(edge)+1到n路径上b的最大值)$

对于动态加边、删边、维护连通性和查询两点最大权值用 LCT 解决。

但是由于 LCT 只能存储点的信息(边不行),所以我们将一条边也看作一个点.若要加上边 $edge$,就相当于 $link(u,edge)$、$link(edge,v)$。

代码

还是挺好写的,$cut$ 的时候写成了 $fa[y]=son[y][0]=0$ 调了好久……偷懒记了一些神奇的东西

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
#include<bits/stdc++.h>
using namespace std;

namespace TYC
{
const int N=1e5+10;
const int inf=0x3f3f3f3f;

inline int read()
{
int x=0,f=0;char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}

struct edge
{
int u,v,a,b;
bool operator < (const edge &t) const
{
return a<t.a;
}
}e[100010];

namespace LinkCutTree
{
int son[N][2],fa[N],val[N],rev[N],id[N],mx[N],idedge[N];
#define ls son[x][0]
#define rs son[x][1]

inline bool isroot(const int &x) {return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}
inline int dir(const int &x) {return son[fa[x]][1]==x;}
inline void reverse(const int &x) {rev[x]^=1,swap(ls,rs);}
inline int Max(const int &x,const int &y) {return val[x]>val[y]?x:y;}
inline void update(const int &x) {mx[x]=Max(Max(mx[ls],mx[rs]),id[x]);}
inline void pushdown(const int &x)
{
if(!rev[x]) return;
if(ls) reverse(ls);
if(rs) reverse(rs);
rev[x]=0;
}

inline void rotate(const int &x)
{
int f=fa[x],d=dir(x);
if(!isroot(f)) son[fa[f]][dir(f)]=x;
fa[x]=fa[f];
son[f][d]=son[x][d^1];
fa[son[x][d^1]]=f;
son[x][d^1]=f,fa[f]=x;
update(f),update(x);
}

inline void splay(const int &x)
{
static int tot,list[N];
list[tot=1]=x;
for(int i=x;!isroot(i);i=fa[i]) list[++tot]=fa[i];
for(int i=tot;i;i--) pushdown(list[i]);
for(;!isroot(x);rotate(x))
if(!isroot(fa[x]))
rotate(dir(x)^dir(fa[x])?x:fa[x]);
}

inline void access(int x)
{
for(int t=0;x;t=x,x=fa[x])
splay(x),son[x][1]=t,update(x);
}

inline void makeroot(const int &x)
{
access(x),splay(x),reverse(x);
}

inline void split(const int &x,const int &y)
{
makeroot(x),access(y),splay(y);
}

inline int find(int x)
{
access(x),splay(x);
while(ls) pushdown(x),x=ls;
return x;
}

inline void link(const int &x,const int &y)
{
makeroot(x);
if(find(y)!=x) fa[x]=y;
}

inline void cut(const int &x,const int &y)
{
split(x,y);
if(son[y][0]!=x||son[x][1]) return;
fa[x]=son[y][0]=0;
update(y);
}

inline int query(const int &x,const int &y)
{
split(x,y);
return mx[y];
}
}

void work()
{
int n=read(),m=read(),ans=inf;
for(int i=1;i<=m;i++)
e[i]=(edge){read(),read(),read(),read()};
sort(e+1,e+1+m);
using namespace LinkCutTree;
for(int i=1,tot=n;i<=m;i++)
{
int u=e[i].u,v=e[i].v,w=e[i].b;
if(find(u)==find(v))
{
int ed=query(u,v);
if(val[ed]<=w) continue;
cut(e[idedge[ed]].u,ed),cut(e[idedge[ed]].v,ed);
val[ed]=w,idedge[ed]=i;
link(u,ed),link(v,ed);
}
else
{
val[++tot]=w,id[tot]=tot;
idedge[tot]=i;
link(u,tot),link(v,tot);
}
if(find(1)==find(n))
ans=min(ans,e[i].a+val[query(1,n)]);
}
printf("%d\n",ans==inf?-1:ans);
}
}

int main()
{
TYC::work();
return 0;
}

一粘代码就显得好长……

参考资料

FlashHu http://www.cnblogs.com/flashhu/p/8324551.html
Candy? https://www.cnblogs.com/candy99/p/6271344.html