RainAir
My OI Blog
RainAir
Link-Cut-Tree 学习笔记

定义

链剖分

首先我们知道,OI 中能见到的有重链剖分,实链剖分和长链剖分。
重链剖分已经在之前的树链剖分中熟练运用过了,长链剖分不常考,所以这次我们先来看一看实链剖分。
实链剖分:将某一个儿子的连边划分为实边,而连向其他子树的边划分为虚边。
我们发现边的虚实是可以动态变化的,因此可以使用更高级、更灵活的 Splay 来维护每一条由若干实边连接而成的实链,基于这个原理,LCT 才能解决很多的动态树问题。
– 查询,修改链信息
– 随意换根
– 动态连边,删边
– 合并树,分离树
– 动态维护连通性
Link-Cut-Tree(简称 LCT) 的性质如下:
1. 每一个 Splay 维护的是一条从上到下按在原树中深度严格递增的路径,且中序遍历 Splay 得到的每个点的深度序列严格递增
2. 每个节点包含且仅包含在一个 Splay 中
3. 实边是包含在 Splay 中的,而虚边是节点连向另一个 Splay 的边。

操作

Access 操作

这是 LCT 的核心操作,其他的操作都是基于此完成的。
这个操作就是在满足 LCT 性质的前提下,将任意一个节点和根节点之间的路径变成一条实链。
下面的图参考YangZhe的论文
一开始我们有一个这样的树(虚线表示虚边)
https://blog.aor.sd.cn/wp-content/uploads/2019/01/1309909-20180123095924037-1618037447.png
那么 LCT 有可能如下图所示(每个框里的元素都在一个 Splay 中)
https://blog.aor.sd.cn/wp-content/uploads/2019/01/1309909-20180123095955350-1680422636.png
现在我们要执行 access(N) 操作了。
由性质 2 可得为了使得 A 到 N 上全是实边,需要使得其他的边变成虚边。
所以可能划分成这样:
https://blog.aor.sd.cn/wp-content/uploads/2019/01/1309909-20180123101901740-2118178734.png
怎么实现这一个过程呢?我们可以让 N 点一直跳 Splay 来实现。
首先执行 Splay(N) 将 N 伸展为根节点,为了满足性质二,$N-O$ 要变为轻边。
为了满足性质一:单方面将 N 的右儿子设置为空。
然后变成下图:
https://blog.aor.sd.cn/wp-content/uploads/2019/01/1309909-20180123110136115-1112016464.png
我们接着把 N 指向的点 I 也伸展到它所属的 Splay 的根节点,为了维护性质,I 到 K 的边要单方面废除,这时候 I 到 L 可以变成实边了,按照性质 1 将 N 放在 I 的右儿子上。
https://blog.aor.sd.cn/wp-content/uploads/2019/01/1309909-20180123110156272-1242463729.png
多次重复该过程直到路径上全为实边。
https://blog.aor.sd.cn/wp-content/uploads/2019/01/1309909-20180123110209772-2057141058.pnghttps://blog.aor.sd.cn/wp-content/uploads/2019/01/1309909-20180123110213709-49169640.png
归纳一下上述过程:
1. 伸展到当前 Splay 的根节点
2. 交换儿子
3. 更新信息(pushup)
4. 操作点换为轻边指向的父亲,转1

makeroot 操作

钦定新根操作。我们在运用中有可能查询两点路径无论如何不可能在一个 Splay 中,这个时候我们考虑改变树的根而保持树维护信息不变,将其放在一个 Splay 里求解。
首先一定要让 $x$ 和 $root$ 在一个 Splay 里,然后将 $x$ 伸展到根。然后注意到一开始 $x$ 的深度是最大的,那么我们如果翻转整个 Splay,$x$ 就变成了深度最小的节点(即根),所以我们打个标记翻转即可。

findroot 操作

查询根节点操作,主要用来判断连通性。
大概就是先让 $x$ 成为 Splay 中的根,然后按照定义一一直走左儿子,最后的那个点一定是深度最小的(即根)。

split 操作

我们想将 $x$ 到 $y$ 的路径放入一个 Splay 里,需要借助 makeroot 操作进行实现。
直接将 $x$ 钦定为根,然后将 $y$ 放入和 $x$ 一样的 Splay 里并伸展为 Splay 的根节点,这样我们查询路径信息其实就是查询 $y$ 的信息了 qwq。

link 操作

连边操作。特判如果这条边不存在直接加一条虚边。

cut 操作

删除一条边。注意到这里特判比较多,即特判以下情况:
1. 不存在这条边
2. $x$ 的父亲不是 $y$,即 $x$ 和 $y$ 虽然在一个 Splay 中但是没有连边。
3. $x$ 的右子树非空,这时以 $y$ 为根开始的中序遍历中 $x$ 和 $y$ 不在一起,即没有边。

此外还要注意 LCT 中的 Splay 和日常写的有些不一样,有些地方是要判断的。
注意 findroot 判断连通性很慢,如果题目只有合并操作的话,建议使用并查集。

完整代码

题目链接

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/397
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

  • https://secure.gravatar.com/avatar/862220ef654838e732ad299cfbca7ab7?s=80&d=mm&r=g
    Langlangago

    Orz

    8月前回复

RainAir

Link-Cut-Tree 学习笔记
定义 链剖分 首先我们知道,OI 中能见到的有重链剖分,实链剖分和长链剖分。 重链剖分已经在之前的树链剖分中熟练运用过了,长链剖分不常考,所以这次我们先来看一看实链剖分。 实链剖…
扫描二维码继续阅读
2019-01-06
标签
近期评论