LCT算法介绍

· · 个人记录

Part 1：introdution

LCT是个啥？

LCT是一种强大的数据结构，可以维护动态森林，也就是对于加点，删点的情况也可以处理树，使其复杂度仍为 \log n。

它的本质是：实链剖分。它与重链剖分有一定的相似，但功能更强。

既然是实，那么就说明它对于变化的情况可以自适应的剖。

在实链剖分的基础下，LCT可以支持更多的操作：

·查询、修改链上的信息（最值，总和等）

·随意指定原树的根（即换根）

·动态连边、删边

·合并两棵树、分离一棵树

·动态维护连通性

Part 2:算法讲解。

前置芝士： Splay 。

对于同一条链（满足深度递增）用 Splay 维护，而对于链的 Splay 根节点指向整条链的父亲，而父亲却不记录儿子。

具体而言，这个 splay 满足其中序遍历的节点深度递增。

核心： access 操作。

对于一个点 u ,可以将其到根的路径提取至一个 splay 中。

首先将 u 更深的节点”自立门户“，具体而言，在 splay 操作中将 u 旋转至根，再让右侧子树（深度更深）自立门户。

然后，来到这条链的父亲，将这条链与父亲的连接”“打通”，同时也需将父亲的更深节点“自立门户”。

这样递归进行直至到根。

上图：

（途中标黑的边为链）

进行断边：

进行连边：

这样就完成了。

代码其实很短，可以自行写一下。

复杂度分析：

每次剖时相当于在到根的链上做 splay

累加势能，相当于在一颗 splay 上旋转：复杂度 \mathcal O(n \log n)

分操作：

  1. makeroot

可以将一个点 u 置为当前根。

操作：先执行一次 access 操作，将 u 与根连在同一链上。

发现每条链只认它的父亲，也就是说，对于除了该链上的链无需操作。

只需将 u 所连的链父边反转即可，这在 splay 中可将整棵树反转来处理（考虑深度变化，即原本的深度大变为深度小）。

  1. split

可以将两个点 u,v 连在一个链上，并以 v 为根。

操作：先将 u 为根，再 access(v) ,最后将 v 在 splay 中旋转上去即可。

  1. findroot

可以查询 u 所在树根。

操作：先 access(u) 在取出深度最浅的点就好了（别忘了懒标记）。

操作完后还要将 u 旋转至根，否则复杂度退化。

（其实可以发现，有关链的操作在最后都要进行 splay ,为的是防止复杂度退化）

  1. cut

可以删去 u \leftrightarrow v 这条边。

操作： 先 split(u,v) ，发现 u,v 必直接连接，此时 splay 中 v 的左子树有且仅有 u ,否则这条边不存在。

那么删除一切的父子关系即可。

  1. link

可以连边 u \leftrightarrow v 这条边。

操作： 先 makeroot(u) 让 u 变为整棵树的根，若 findroot(v)=u ，则已在同一棵树上，无需操作。

否则将 u 所在的链的父亲认为 v 即可。