Link-cut-tree学习总结
Link-Cut-Tree(简称LCT)是解决动态树类问题一种数据结构。把重链用Splay表示的思想非常有趣。
LCT是由Tarjan发明的(又是他
LCT的基础是Splay,但是二者不完全相同,直接套Splay的模板是很容易出错的= =
假如我们要解决一个问题,维护一个序列,支持下列操作:
区间求和
区间求最值
区间修改
求连续子段和
直接线段树就行了
假如这个呢
维护一个序列,支持下列操作:
区间求和
区间求最值
区间修改
求连续子段和
添加一段区间
删除一段区间
翻转一段区间
那就只能用Splay了。例题:NOI2005 D1T2 维修序列
假如我们把操作都移到树上:
维护一棵树,支持下列操作:
链上求和
链上求最值
链上修改
子树修改
子树求和
换根
这就可以用树链剖分解决了
那么这个呢
维护一棵树,支持下列操作:
链上求和
链上求最值
链上修改
断开树上的一条边
连接两个点,保证连接后仍然是一棵树
这就是一个简单的动态树问题
由于树是动态的,我们不能每次操作都重标号一遍,树链剖分搞不了
然而我们可以沿用树链剖分的轻重链剖分的概念
既然是动态那么我们肯定要把静态的线段树换成动态的Splay
于是就有LCT=树链剖分+Splay
引入一些概念:
Preferred Child:重儿子(为了便于理解这里沿用树链剖分中的命名),重儿子与父亲节点同在一棵Splay中,一个节点最多只能有一个重儿子
Preferred Edge:重(zhòng)边,连接父亲节点和重儿子的边
Preferred Path:重链,由重边及重边连接的节点构成的链
Auxiliary Tree(辅助树):由一条重链上的所有节点所构成的Splay称作这条链的辅助树
在辅助树上,每个点的键值为这个点的深度,即这棵Splay的中序遍历是这条链从链顶到链底的所有节点构成的序列
辅助树的根节点的父亲指向链顶的父亲节点,然而链顶的父亲节点的儿子并不指向辅助树的根节点
原树中的重链:辅助树中两个节点位于同一棵Splay中
原树中的轻链:辅助树中子节点所在Splay的根节点的father指向父节点
注意原树与辅助树的结构并不相同
辅助树的根节点≠原树的根节点
辅助树中的father≠原树中的father
由于要维护的信息已经都在辅助树中维护了,所以LCT无需维护原树,只维护辅助树即可
轻链和重链并不是固定的,随着算法的进行,轻链和重链随算法需要和题目要求而变化,然而无论怎么变化,由这棵辅助树一定能生成原树,并满足辅助树的所有性质
下面就是一些操作:
Splay部分
1.is_root
int is_root(int x){return ch[f[x]][1]!=x && ch[f[x]][0]!=x;}
它的作用就是判断一下x是否是根,因为假如它是根的话在辅助树中它的父亲的孩子就是自己。
2.pushdown
void pushdown(int x) { if (res[x] && x) { if (ch[x][0]) res[ch[x][0]]^=1; if (ch[x][1]) res[ch[x][1]]^=1; swap(ch[x][1],ch[x][0]); res[x]=0; } }
这个操作是下推反转标记,置于为什么有反转标记,下面会讲。
3.splay
int get_son(int x){return ch[f[x]][1]==x;} void rot(int x) { int fa=f[x],fafa=f[fa],k=get_son(x); if (!is_root(fa)) ch[fafa][ch[fafa][1]==fa]=x; ch[fa][k]=ch[x][k^1],f[ch[fa][k]]=fa; ch[x][k^1]=fa,f[fa]=x; f[x]=fafa; update(fa);update(x); } void push(int x) { if(!is_root(x)) push(f[x]); pushdown(x); } void splay(int x) { push(x); for (int fa;!is_root(x);rot(x)) if (!is_root(fa=f[x])) rot(get_son(x)==get_son(fa)?fa:x); }
在Splay前,要把x到根上的路径pushdown。
注意第5行的部分,这个不能放到后面,要不会死循环。
因为假如你放的了后面,它的父子关系就已经改变了,不是直接判断is_root。
LCT操作
1.access
void access(int x) { for (int y=0;x;y=x,x=f[x]) splay(x),ch[x][1]=y; }
Access(一些版本中也叫做Expose)函数,是LCT各种姿势的基础
Access函数的作用是:将一个点与原先的重儿子切断,并使这个点到根路径上的边全都变为重边
即执行Access(x)函数后这个节点到根的路径上的所有节点形成了一棵Splay
便于操作或查询节点到根路径上的所有节点
一个例子:
access以前的树
具体实现:根据辅助树按照深度为关键字的性质,重建一颗splay。不断地将一个结点的父亲转到根,然后把这个结点接到它父亲的右儿子。
2.make_root
把x换成根
void make_root(int x){access(x),splay(x),res[x]^=1;}
作用:将x设为原树的根
有向树没有这个操作
注意Access(x)之后x只是辅助树的总根,并不是原树的根,因为Access(x)之后x还有左子树,左子树的深度小于x,故x不是根节点
发现x设为根之后,原先x到根的路径上点的深度正好反转
于是只需要在Access+Splay之后翻转即可
具体实现:因为原树是虚树,所以在原树中进行变换实际上是在辅助树中进行变换。首先Access一个点,再将这个点在辅助树中转到根。又是根据辅助书按照深度为关键字的性质,将这个点所在的splay树反转,实际上改变了深度的关系,也就是实现的原树的换根。
3.find_root
int find_root(int x) { access(x),splay(x); while(ch[x][0]) x=ch[x][0]; return x; }
它可以找一个点在原树中的根,用于判断两个点的连通性。
具体实现:首先Access这个点,然后在辅助树中将这个点转到根,由于辅助树按照深度为关键字排序,所以不断地向左子树寻找,就可以找到深度最小的根。
4.link
void link(int x,int y){make_root(x),f[x]=y,splay(x);}
它可以将两个不连通的点连通。也可以说把两个树连起来。
具体实现:首先make_root,在原树中将一个点转到那个点所在的树的根。然后将这个转到根的点的father接到另外一个点上。可以进行一次splay来update。【logn不值钱
5.cut
void cut(int x,int y){make_root(x),access(y),splay(y),ch[y][0]=f[x]=0;}
将x和y之间的连边切断
直接将x make_root,然后将y进行Access+Splay,之后x一定在y的左儿子上,直接切断即可
证明:反证法
假设y进行Access+Splay操作时通过双旋将x旋转到y的左儿子的左儿子 那么x和y之间一定有一个节点 故xy之间深度之差不为1 与已知xy之间有连边相矛盾
5.对x到y路径上的点进行修改或查询
只需要对x进行make_root操作,然后对y进行Access+Splay操作,那么x到y路径上的所有点都在以y为根的子树上,之后就随便搞了
至此,我们就写完了LCT的所有操作
例题
#include <cstdio> #define N 10010 using namespace std; #define read(a) a=getnum() inline int getnum() { int ret=0; char c; for(c=getchar(); c<'0' || c>'9'; c=getchar()); for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return ret; } int n,m,x,y,f[N],ch[N][2],siz[N],res[N]; char s[10]; void swap(int &a,int &b){int t=a;a=b;b=t;} void update(int x){siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];} void pushdown(int x) { if (res[x] && x) { if (ch[x][0]) res[ch[x][0]]^=1; if (ch[x][1]) res[ch[x][1]]^=1; swap(ch[x][1],ch[x][0]); res[x]=0; } } int is_root(int x){return ch[f[x]][1]!=x && ch[f[x]][0]!=x;} int get_son(int x){return ch[f[x]][1]==x;} void rot(int x) { int fa=f[x],fafa=f[fa],k=get_son(x); if (!is_root(fa)) ch[fafa][ch[fafa][1]==fa]=x; ch[fa][k]=ch[x][k^1],f[ch[fa][k]]=fa; ch[x][k^1]=fa,f[fa]=x; f[x]=fafa; update(fa);update(x); } void push(int x) { if(!is_root(x)) push(f[x]); pushdown(x); } void splay(int x) { push(x); for (int fa;!is_root(x);rot(x)) if (!is_root(fa=f[x])) rot(get_son(x)==get_son(fa)?fa:x); } void access(int x) { for (int y=0;x;y=x,x=f[x]) splay(x),ch[x][1]=y; } int find_root(int x) { access(x),splay(x); while(ch[x][0]) x=ch[x][0]; return x; } void make_root(int x){access(x),splay(x),res[x]^=1;} void link(int x,int y){make_root(x),f[x]=y,splay(x);} void cut(int x,int y){make_root(x),access(y),splay(y),ch[y][0]=f[x]=0;} main() { read(n);read(m); for (int i=1;i<=m;++i) { scanf("%s",s); read(x);read(y); if (s[0]=='Q') if (find_root(x)==find_root(y)) printf("Yes\n"); else printf("No\n"); if (s[0]=='C') link(x,y); if (s[0]=='D') cut(x,y); } }
The end.