干啥用的?
对于一个森林,查询链上信息、
前置芝士:splay
P3690 【模板】Link Cut Tree (动态树)
(开始大量盗图)
首先确定LCT的一些基本概念
- 实边:每个点最多连一条实边(类似树剖),这个边是随便连的,而且是可以变的、虚边:不是实边的边
- 实链:对于每个实边构成的链(这条链必须是从上到下深度递增),开一个splay,存的是树上的节点,按深度排序(中序遍历为深度递增),平衡树上维护的信息就是这一条链的信息
对于每个节点,\(fa[x]\)表示父亲(实链则表示splay上的父亲,否则表示虚链上的父亲),\(son[x][0/1]\)表示splay上的左右儿子,不记录虚链的儿子
这样判断是否为当前这个splay的根的方法就变为
inline bool is_root(int x){return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}
这一棵树
按splay划分就是
因为有翻转操作(之后会提到哪里会用),所以需要用到文艺平衡树
int son[N][2],val[N],sum[N],tag[N],fa[N];
inline void update(int x){sum[x]=sum[son[x][0]]^sum[son[x][1]]^val[x];}
inline void rev(int x){swap(son[x][1],son[x][0]);tag[x]^=1;}
inline void pushdown(int x){
if(!tag[x])return;tag[x]=0;
if(son[x][0])rev(son[x][0]);
if(son[x][1])rev(son[x][1]);
}
inline int id(int x){return x==son[fa[x]][1];}
inline void rotate(int x){
int f=fa[x],gf=fa[f],idf=id(f),idx=id(x);
if(!is_root(f))son[gf][idf]=x;fa[x]=gf;
son[f][idx]=son[x][idx^1];son[x][idx^1]=f;
if(son[f][idx])fa[son[f][idx]]=f;fa[f]=x;
update(f);update(x);
}
int stac[N],top;
inline void splay(int x){
top=0;int cur=x;stac[++top]=x;
while(!is_root(cur))cur=fa[cur],stac[++top]=cur;
while(top)pushdown(stac[top--]);//从上到下下放标记
while(!is_root(x)){
if(!is_root(fa[x])){
if(id(fa[x])==id(x))rotate(fa[x]);
else rotate(x);
}
rotate(x);
}
}
\(access(x)\)
LCT基本操作,让\(x\)到根的路径上为一条实链
目标:
依次完成:
把自己变为根,断掉原来的儿子,向上
把自己变为根,替换掉原来的儿子,向上
把自己变为根,替换掉原来的儿子,向上
把自己变为根,替换掉原来的儿子,向上
直到合并到根为止
inline void access(int x){
for(int y=0;x;y=x,x=fa[x])
splay(x),son[x][1]=y,update(x);
}
其余操作都在\(splay\)和\(access\)基础上
\(make\_root(x)\)
让\(x\)成为根
先打通\(x\)到根的路径,然后让\(x\)成为当前\(splay\)的根
但是这时的\(splay\)是按深度递增的,没有变,要变成按深度递减,那么就需要把这棵树翻转一下
inline void make_root(int x){
access(x); splay(x); rev(x);
}
\(find\_root(x)\)
找到\(x\)所在树的根
先打通\(x\)到根的路径,找到这个splay的深度最低的点即可(注意\(pushdown\))
inline int find_root(int x){
access(x); splay(x); pushdown(x);
while(son[x][0])x=son[x][0],pushdown(x);
splay(x);
return x;
}
\(link(x,y)\)
先让\(x\)成为根,判断一下\(y\)的根是不是\(x\)
是的话就已经在一棵树内,不用连边
否则连一条虚边
inline void link(int x,int y){
make_root(x);
if(find_root(y)==x)return ;
fa[x]=y;
}
\(cut(x,y)\)
同样的先把\(x\)作为根,判断一下\(y\)在不在\(x\)的子树内
注意这里调用了\(find\_root(y)\),若\(y\)在\(x\)的子树内,那么\(x\)到\(y\)的链已经打通,\(x,y\)在同一颗\(splay\)内,且这棵\(splay\)的根为\(x\)
那么如果\(y\)与\(x\)有连边,那么\(y\)的深度等于\(dep[x]+1\),又因为splay维护一条链的信息,这个\(dep[x]+1=dep[y]\)的点事唯一的,即\(y\)一定是\(x\)的右儿子,且\(y\)没有左儿子(不存在在\(x,y\)之间的点)
inline void cut(int x,int y){
make_root(x);
if(find_root(y)!=x||fa[y]!=x||son[y][0])return;
fa[y]=son[x][1]=0;update(x);
return ;
}
\(query(x,y)\)
以\(x\)为根,连上\(x,y\)的边,以\(x/y\)为splay的根
这样跟的信息就是整条链的信息
inline int query(int x,int y){
make_root(x);access(y);splay(y);
return sum[y];
}
\(modify(x,val)\)
修改信息
即把\(x\)作为其所在\(splay\)的根,然后跟新自己的\(val\),最后\(update\)即可
inline void modify(int x,int v){
splay(x);val[x]=v;update(x);
}