【学习笔记】 - 基础数据结构 :Link-Cut Tree - Vsinger_洛天依
source link: https://www.cnblogs.com/Vsinger-LuoTianYi/p/18029661
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
发现树剖代码太长了,给我恶心坏了
学个代码短点的能写树剖题的数据结构吧
简介以及优缺点介绍
Link-Cut Tree
,也就是LCT
,一般用于解决动态树问题
Link-Cut Tree
可用于实现重链剖分的绝大多数问题,复杂度为\(O(n \log n)\),看起来比树剖的\(O(n \log^2 n)\)复杂度更小,但则不然,基于splay
实现的Link-Cut Tree
常数巨大(约11
倍常数),往往表现不如树剖
Link-Cut Tree
的代码往往比树剖少一些
动态树问题
维护一个森林,支持删除某条边,连接某条边,并保证加边/删边之后仍是森林
同时维护这个森林的一些信息
-
回顾重链剖分
-
按子树大小剖分整棵树并重新标号
-
此时树上形成了一些以链为单位的连续区间,用线段树进行区间操作
-
我们发现,诶重剖怎么是按子树大小来剖的,这也不能搞动态树啊
显然我们需要让剖分的链是我们指定的链,以便利用来求解
-
对于一个点连向它所有儿子的边,我们自己选择一条边进行剖分,我们称被选择的边为实边,其他边则为虚边。
我们称实边所连接的儿子为实儿子,实边组成的链称之为实链
选择实链剖分的最重要的原因便是因为实链是我们选择的,灵活且可变
正是它的这种灵活可变性,用
Splay
来维护这些实链
Link-Cut Tree
我们可以把 LCT
理解为用一些 Splay
来维护动态树剖并实现动态树上的区间操作
每条实链都建一个 Splay
维护整个链的区间信息
-
我们认为一些
Splay
共同构成了一颗辅助树,每个辅助树都维护了一颗树,所有的辅助树构成了Link-Cut Tree
,维护了整个森林辅助树有很多性质
-
辅助树由多棵
Splay
组成,每棵Splay
都维护了树中一条严格在原树中「从上到下」深度单调递增的路径,且中序遍历这棵Splay
得到的点的深度序列单调递增 -
原本的树的每个节点与辅助树的
Splay
节点一一对应。 -
辅助树各棵
Splay
间并不独立。在LCT
中每棵Splay
的根节点的父亲节点指向原树中这条链的父亲节点(即链最顶端的点的父亲节点)。特殊的,这里的儿子认父亲,父亲却不认儿子,对应原树的一条 虚边
故每个连通块恰好有一个点的父亲节点为空
-
维护任何操作都不需要维护原树
辅助树可以在任何情况下拿出一个唯一的原树
只需维护辅助树即可
这是一颗原树 \(\gets\)
这是建出的辅助树 \(\gets\)
-
这里只有 LCT
特有的几个操作
-
fa[x] //x的父亲节点 son[x][2] //x的左右儿子 sz[x] //x的子树大小 rev[x] //x是否需要对儿子进行翻转
-
splay
操作和正常
splay
不同的是LCT
的每次splay
影响的所有点都必须是当前splay
中的钱而且在
splay
操作前必须把它的所有祖先全都pushdown
,因为LCT
不一定把哪个点应用splay
操作-
inline bool isroot(int x){ return ((son[fa[x]][0]==x)||(son[fa[x]][1]==x)); } inline void splay(int x){ int y=x,z=0; st[++z]=y; while(isroot(y)){ st[++z]=y=fa[y]; } while(z){ push_down(st[z--]); } while(isroot(x)){ y=fa[x],z=fa[y]; if(isroot(y)) rotate((son[y][0]==x)^(son[z][0]==y)?x:y); rotate(x); } push_up(x); }
-
-
access
操作LCT
最重要的操作,其他所有操作都要用到它含义是访问某节点,作用是对于访问的节点 \(x\) 打通一条从树根到 \(x\) 的实链
如果有其他实边与新的实链相连则改为轻边
可以理解为专门开辟一条从 \(x\) 到 \(root\) 的路径,用
splay
来维护这条路径-
先把 \(x\) 旋转到所在
Splay
的根用 \(y\) 记录上一次的 \(x\) (初始化\(y=0\)),把 \(y\) 接到 \(x\) 的右儿子上
这样就把上一次的实链接到了当前实链下
它原来的右儿子(也就是
LCT
树中在 \(x\) 下方的点)与它所有的边自然变成了虚边记得
pushup
-
inline void access(int x){ for(int y=0;x;x=fa[y=x]) splay(x), rc=y,push_up(x); }
-
-
作用是把某个节点变成树根(这里的根指的是整颗
LCT
的根)再加上
access
操作就能方便的提取出LCT
上两点之间距离提取\(u\)到\(v\)的路径只需要
toroot(u),access(v)
,然后\(v\)所在的Splay
对应的链就是\(u\)到\(v\)的路径-
先
access
一下,这样 \(x\) 就一路打通到了根,然后再splay(x)
,由于x
是这条实链最下面的点,所以 \(x\) 的splay
的右儿子是空的,左儿子是它上面所有点因为
splay
是支持区间翻转的,所以只要给x打个翻转标记就翻转到根了 -
inline void toroot(int x){ access(x); splay(x); reserve(x); }
-
-
link
操作作用是链接两个辅助树,对于
link(u,v)
,表示 \(u\) 所在的辅助树和 \(v\) 所在的辅助树-
只需要先
toroot(u)
,然后记fa[u]=v
就可以了,就是把一整颗辅助树连到另一个点上 -
inline void link(int x,int y){ toroot(x); if(Find(y)!=x) fa[x]=y; }
-
-
cut
操作这个操作作用是切断某条边
-
先分离出 \(x\) 到 \(y\) 的这条链
我们假设切断的点一定是相邻的(不相邻的特判掉),然后把 \(y\) 的左儿子(也就是
LCT
中 \(y\) 的父亲)与 \(y\) 的边断掉就好了 -
inline void split(int x,int y){ toroot(x); access(y); splay(y); } inline int Find(int x){ access(x); splay(x); while(lc) push_down(x),x=lc; splay(x); return x; } inline void cut(int x,int y){ toroot(x); if(Find(y)==x&&fa[y]==x&&!son[y][0]){ fa[y]=son[x][1]=0; push_up(x); } }
-
点击查看代码
#define lc son[x][0]
#define rc son[x][1]
int fa[N],son[N][2],val[N],ans[N],st[N];
bool rev[N];
inline bool isroot(int x){
return ((son[fa[x]][0]==x)||(son[fa[x]][1]==x));
}
inline void push_up(int x){
ans[x]=ans[lc]^ans[rc]^val[x];
}
inline void reserve(int x){
int t=lc;
lc=rc;rc=t;
rev[x]^=1;
}
inline void push_down(int x){
if(rev[x]){
if(lc)reserve(lc);
if(rc)reserve(rc);
rev[x]=0;
}
}
inline void rotate(int x){
int y=fa[x],z=fa[y],k=son[y][1]==x,w=son[x][!k];
if(isroot(y))
son[z][son[z][1]==y]=x;
son[x][!k]=y;
son[y][k]=w;
if(w)
fa[w]=y;
fa[y]=x;fa[x]=z;
push_up(y);
}
inline void splay(int x){
int y=x,z=0;
st[++z]=y;
while(isroot(y)){
st[++z]=y=fa[y];
}
while(z){
push_down(st[z--]);
}
while(isroot(x)){
y=fa[x],z=fa[y];
if(isroot(y))
rotate((son[y][0]==x)^(son[z][0]==y)?x:y);
rotate(x);
}
push_up(x);
}
inline void access(int x){
for(int y=0;x;x=fa[y=x])
splay(x),
rc=y,push_up(x);
}
inline void toroot(int x){
access(x);
splay(x);
reserve(x);
}
inline int Find(int x){
access(x);
splay(x);
while(lc)
push_down(x),x=lc;
splay(x);
return x;
}
inline void split(int x,int y){
toroot(x);
access(y);
splay(y);
}
inline void link(int x,int y){
toroot(x);
if(Find(y)!=x)
fa[x]=y;
}
inline void cut(int x,int y){
toroot(x);
if(Find(y)==x&&fa[y]==x&&!son[y][0]){
fa[y]=son[x][1]=0;
push_up(x);
}
}
signed main(){
int n,m;FastI>>n>>m;
for(int i=1;i<=n;++i)
FastI>>val[i];
while(m--){
int opt,x,y;
FastI>>opt>>x>>y;
if(opt==0){
split(x,y);
FastO<<ans[y]<<endl;
}
else if(opt==1){
link(x,y);
}
else if(opt==2){
cut(x,y);
}
else if(opt==3){
splay(x);
val[x]=y;
}
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK