首页 > 笔记 > Link-cut-tree学习总结

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的中序遍历是这条链从链顶到链底的所有节点构成的序列

辅助树的根节点的父亲指向链顶的父亲节点,然而链顶的父亲节点的儿子并不指向辅助树的根节点

images

原树中的重链:辅助树中两个节点位于同一棵Splay中
原树中的轻链:辅助树中子节点所在Splay的根节点的father指向父节点

注意原树与辅助树的结构并不相同

辅助树的根节点≠原树的根节点
辅助树中的father≠原树中的father

由于要维护的信息已经都在辅助树中维护了,所以LCT无需维护原树,只维护辅助树即可

轻链和重链并不是固定的,随着算法的进行,轻链和重链随算法需要和题目要求而变化,然而无论怎么变化,由这棵辅助树一定能生成原树,并满足辅助树的所有性质

 

下面就是一些操作:

Splay部分

1.is_root

它的作用就是判断一下x是否是根,因为假如它是根的话在辅助树中它的父亲的孩子就是自己。

2.pushdown

这个操作是下推反转标记,置于为什么有反转标记,下面会讲。

3.splay

在Splay前,要把x到根上的路径pushdown。

注意第5行的部分,这个不能放到后面,要不会死循环。

因为假如你放的了后面,它的父子关系就已经改变了,不是直接判断is_root。

LCT操作

1.access

Access(一些版本中也叫做Expose)函数,是LCT各种姿势的基础

Access函数的作用是:将一个点与原先的重儿子切断,并使这个点到根路径上的边全都变为重边

即执行Access(x)函数后这个节点到根的路径上的所有节点形成了一棵Splay

便于操作或查询节点到根路径上的所有节点

一个例子:

images

access以前的树

images

具体实现:根据辅助树按照深度为关键字的性质,重建一颗splay。不断地将一个结点的父亲转到根,然后把这个结点接到它父亲的右儿子。

2.make_root

把x换成根

作用:将x设为原树的根

有向树没有这个操作

注意Access(x)之后x只是辅助树的总根,并不是原树的根,因为Access(x)之后x还有左子树,左子树的深度小于x,故x不是根节点

发现x设为根之后,原先x到根的路径上点的深度正好反转

于是只需要在Access+Splay之后翻转即可

具体实现:因为原树是虚树,所以在原树中进行变换实际上是在辅助树中进行变换。首先Access一个点,再将这个点在辅助树中转到根。又是根据辅助书按照深度为关键字的性质,将这个点所在的splay树反转,实际上改变了深度的关系,也就是实现的原树的换根。

3.find_root

它可以找一个点在原树中的根,用于判断两个点的连通性。

具体实现:首先Access这个点,然后在辅助树中将这个点转到根,由于辅助树按照深度为关键字排序,所以不断地向左子树寻找,就可以找到深度最小的根。

4.link

它可以将两个不连通的点连通。也可以说把两个树连起来。

具体实现:首先make_root,在原树中将一个点转到那个点所在的树的根。然后将这个转到根的点的father接到另外一个点上。可以进行一次splay来update。【logn不值钱

5.cut

将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的所有操作

例题

bzoj2049

The end.


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×