发现树剖代码太长了,给我恶心坏了
学个代码短点的能写树剖题的数据结构吧
前置知识
-
树链剖分
简介以及优缺点介绍
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;
}
}
}