LCT总结（个人笔记）
柒葉灬
·
2019-03-10 14:46:24
·
个人记录
LCT总结
前置技能：splay
介绍：
LCT即 Link-Cut-Tree，
其中Link指连接，Cut指断开，Tree则是一棵树。
说白了就是一棵动态树，
可以动态删除边，添加边。
擅长处理链上的问题，
但是子树问题也可以解决，后面会有例题。
当然，作为一个优秀的数据结构LCT，
肯定不能像普通的树一样暴力跳父亲，
肯定要有优秀的方法快速找根。
但普通的树是用 倍增 和 重链剖分。
(或许还有长链剖分
而这两种算法都不能修改。
所以我们用的是另一种方法：实链剖分
实链剖分
这里先介绍一下什么是 实链剖分 。
实际上就是选一个儿子与自己的边当做实边，
其他边都是虚边
实边需要满足什么条件？
实边不需要任何条件，
就是自己随便选的，
就是因为是随便选的，所以才可以动态连边删边。
这些实边就形成了实链。
当然也可以都是虚边
我之前在一篇博客里面看到一句话，
很好的概括了实边和虚边的区别：
认子不认父
即每个点不用管自己和父亲连的是实边还是虚边，
只要记录与哪一个儿子连实边就行了。
如果需要判断自己和父亲是不是连实边
只需要判一下父亲的实儿子是不是自己就行了
感觉有什么怪怪的？？？
那么有了实链之后有什么用？
怎么把实链用在LCT上？
想一下如果是重链剖分的话，应该怎么找根呢？
我们可以一直跳到实链的顶端，直到到达根为止。
但是这样还有几个问题需要解决：
怎么保证跳的实链的次数不会过大？
怎么跳到每条链的顶端的父亲？
第一个问题：怎么保证跳的实链的次数不会过大？
我们可以每次把当前的点和根变成一条实链，
以此来保证复杂度的合理性。（感性理解）
第二个问题：怎么跳到每条链的顶端的父亲？
重链剖分里面是直接记录每一个点的top指向哪里。
而实链剖分就不能这么做，因为top随时可能会变。
这时候就要用到最核心的知识了，
把每一条实链用一个splay来表示：
左儿子深度都比当前点浅
右儿子深度都比当前点深
splay当中最左边的数就是链的顶端了。
但，链顶的点不一定是splay的根怎么办？
即，可能链顶的点的fa表示的是splay当中的fa
我们注意到，splay当中，根是没有父亲的。
所以我们可以这么做，
每个splay的根的fa表示链顶的点在树中的父亲
做个图以便理解：
其中加粗的是实边，其他的是虚边。
而实际上每一个实链是用splay来表示的，
所以可能实际上son和fa的关系是这样的。
其中每一个框就是一个splay
？mmp为什么写了半天的概念
接下来就是怎么设计代码了。
多了一个判断是不是$splay$的根的函数$noroot
bool noroot(int x){
return son[fa[x]][0]==x||son[fa[x]][1]==x;
}//如果不是splay的根返回true;
首先，LCT当中的splay的rotate和splay
是不能复制普通splay的，
有些不同。
rotate操作
void rotate(int x){
int y=fa[x];
int z=fa[y];
int k=(son[y][1]==x);
if(noroot(y))son[z][(son[z][1]==y)]=x;
fa[x]=z;
son[y][k]=son[x][k^1];
fa[son[x][k^1]]=y;
son[x][k^1]=y;
fa[y]=x;
up(y);up(x);
}
为什么需要判断noroot(y)呢？
因为如果y是根则说明z不在x这个splay内
如果不加则会改变z的实儿子，故错。
splay操作
void splay(int x){
int u=x,top=0;
stk[++top]=u;
while(noroot(u))stk[++top]=u=fa[u];
while(top)down(stk[top--]);
//即先down完之后再splay
while(noroot(x)){
int y=fa[x];
int z=fa[y];
if(noroot(y))
(son[z][1]==y)^(son[y][1]==x)?rotate(x):rotate(y);
rotate(x);
}
}
以上都是处理实链的操作，那么怎么造出实链呢？
下面这个操作就是LCT的核心操作了。
access操作
void access(int x){
for(int y=0;x;y=x,x=fa[x])
splay(x),son[x][1]=y,up(x);
}
这段代码什么意思呢？
即造出x到root这条实链，之前的其他实边变为虚边。
循环里面是把x与y连上实边，之前的实边被覆盖。
注意链是从root到x的，
所以x实际上位于实链的最底端，splay的最右端。
接下来的代码想想就都能明白了
makeroot操作
void makeroot(int x){
access(x);splay(x);pushr(x);
}
把x变成树的根。
findroot操作
int findroot(int x){
access(x);splay(x);
while(son[x][0])down(x),x=son[x][0];
splay(x);//保证复杂度
return x;
}
还有一个操作可以把要修改的链给拎出来
split操作
void split(int x,int y){
makeroot(x);access(y);splay(y);
//直接对y节点进行询问即可
}
最后就是连边和删边操作了
link操作
所连的边可能已经存在了，那么这么写
bool link(int x,int y){
makeroot(x);
if(findroot(y)==x)return false;
fa[x]=y;//直接连接虚边
return true;
}
如果数据中保证边合法，那么可以这么写
void link(int x,int y){
makeroot(x);
fa[x]=y;
}
cut操作
所删的边可能不存在，需要这么写
bool cut(int x,int y){
makeroot(x);
if(findroot(y)!=x||fa[y]!=x||son[y][0])return false;
son[x][1]=fa[y]=0;
up(x);
return true;
}
如果数据中保证边合法，那么可以这么写
void cut(int x,int y){
split(x,y);
son[y][0]=fa[x]=0;
up(y);
}
那么LCT基本就已经讲完了，接下来就是做题经验了。
LCT在基环树当中的应用
基环树当中有一个环，但显然树里面不能有环，
所以可以用LCT把基环树变成树。
即把环中的一个点变成根，
再把连成环的那条边单独记录下来，
如果环被破坏掉了则连回去。
LCT专题L
LCT维护子树信息
只不过略微麻烦一点，
就是多维护一个虚儿子的信息，
在$access$的时候注意修改就行了。
[LCT专题K](https://cn.vjudge.net/contest/282972#problem/K)
------
END