Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

01/5
21:35
图论 学习笔记

LCT学习笔记

什么是LCT?

LCT:link-cut-tree 动态树 用来维护树或者森林

在LCT中引用了轻重链的思想,有这么几个概念:

  • Preferred Child 偏好子节点
  • Preferred Edge 偏好边
  • Preferred Path 偏好路径
  • Auxiliary Tree 辅助树

例如:

根节点1的preferred child是2,那么边1-2是一条preferred edge,2的preferred child是6,那么从节点1到节点6的路径是一条preferred path。 3、4、5、6没有preferred child。

1-2-6就被拆成了一条链,3、4、5各自是一条链。

那么什么是Auxiliary Tree(辅助树)呢?

Auxiliary Tree 是将这些链上的节点以深度为关键字而建成的一颗颗splay树。

就拿刚才的例子来说,它的Auxiliary Tree就是:

这里还有一个概念就是 Path Parent 路径父节点,即一条树链组成的splay的根节点与另一棵splay树连接的节点。如3节点的Path Parent 是1节点。

这样再用数据结构来加速的话,时间效率能达到log 级,貌似这也是树链剖分的原理。

LCT的基本操作

一、Access(访问)

Access操作称得上是LCT所有操作的基础。如果access了某个节点,则该节点到根节点上的所有节点都变成了preferred child,所有的边都变成了 preferred edge,这条路径也变成了 preferred path。而这条树链就加入了根节点的Auxiliary Tree中。

具体操作:将访问的点splay到Auxiliary Tree根的位置,然后断开右儿子(因为被访问的点没有 preferred child);然后访问它的Path Parent,将其splay到Auxiliary Tree根的位置,断开右儿子,连到访问的节点上,一直重复这个过程。

还是之前的那棵树,看一下access(3)过程中的变化:

初始的Auxiliary Tree:

将3节点splay到根的位置,断开右儿子,没什么变化……

然后访问3节点的Path Parent 1节点,将其splay到根的位置,断开右儿子,并与3节点连接。变化如下:

原树变化如下:

二、Makeroot(换根)

只需access(x),splay(x),再反转就好了。

先将u节点splay到根的位置,然后将u的Path Parent设为v即可。

四、Cut(拆分)

先将u节点splay到根的位置,然后access(v),splay(v),再断开u与v的联系即可。

LCT中splay的写法注意

一、isroot()

一般splay的写法,判断一个节点是不是根节点只要看它的父节点是不是NULL即可。

而在LCT中,因为涉及多棵splay树,一棵splay树的根节点可能连向另一颗splay树。

二、rotate()

三、splay()

就先到这吧…