【总结】Link-Cut Tree

2023-08-19 10:56:04

这是一篇关于LCT的总结

加删边的好朋友——Link Cut Tree

Link-Cut Tree，LCT的全称

可以说是从树剖引出的问题

树剖可以解决静态的修改或查询树的链上信息；那如果图会不断改变，怎么办？

然后就有了LCT（真不知道发明它和它的那些拓展用法的人是怎么想出来的，创造力真强）

LCT要做的就是在不断的加边、删边等等改变图的操作中维护树的信息

不得不说，它很强大

本篇随笔只是记录一下自己对使用LCT的心得，如果你想从头开始学习LCT，可以去这里—— LCT总结+题单+洛谷P3690[模板]Link Cut Tree(动态树)(LCT,Splay)

什么时候需要LCT？

一般情况下，如果题目中有加/删边的操作，那就套LCT进去，然后思考怎么用LCT完成其余的操作

不过真正的好题是完全看不出要用LCT的，所以更好的方法是先想到算法，然后用LCT维护算法中支持LCT维护的东西（数据结构其实本应这样用）

LCT的强大的操作们

动态维护树中的联通性

这是最简单的操作了，该link的link，该cut的cut，询问的时候，两个点都findroot一下，相同的话就是联通的，反之不联通

动态维护树的链上信息

这个也算是基本操作了，要找一条 \(u\) 到 \(v\) 的链，就先把 \(u\) makeroot到根，然后access一下 \(v\) （其实就是split），Splay维护好要维护的信息就行

动态维护图的生成树

这里开始就变成图了，不再单纯是树了

有时从题目中发现性质是要动态维护图的最大/小生成树（什么是动态？就是要维护正确性，那么在一个条件下，只有一些边在图中，其它的边不能够连）

其实就是四个字，化边为点

把原图的每一条边看成是一个点，那么 \(u\) 连到 \(v\) ，就变成了 \(u\) 连到了 \(s\) ， \(s\) 再连到 \(v\) ，然后边权存在那条边化为的点上，其他的原图中真正的点对应的点没有点权，这样一条边如果加入了，那么它在Splay中就会有自己的贡献，如果要删掉，就断开它化为的点与这条边两端的点，自然就不会有它的答案计入

动态维护图的边双

这个东西算是比较玄学的了

加边的时候，发现这条边的两端如果已经联通，那么这条边加入后就一定会形成一个环，那么这个环里的所有点就处在一个边双里

怎么维护？

用另一个点表示这个边双（所有边双都新开一个点来表示），如果发现环，就把这个环里的所有点的父亲指向新点（一个dfs搞定），表示这些点已经归于一个边双了，然后这之中的所有点的操作都由新点代理进行，是不是很类似缩点，其实它就是缩点

很玄学，多看代码

动态维护树的子树信息

又回到树了，但是这也是最玄的

LCT是把一条链变成一个Splay，所以无论怎么搞，LCT里最终维护都是一条链上的信息，那如果题目要维护原树的子树信息，又要动态加边、删边怎么办？

那不随便，不管，还是LCT

注意LCT的构造，原树中一个节点的儿子（除实儿子）在LCT中一定是这个节点的虚儿子，那么如果要知道这个节点的原树信息，就是原树中的实儿子信息加虚儿子信息，实儿子信息LCT本身可以维护；那就只要知道虚儿子信息怎么维护。

这个还是简单的，一个数组搞定。LCT虽然一个节点只认一个儿子，但它的所有儿子都是认它的。所以对于儿子，把自己的信息加到父亲上去就搞定了

可以看看链接的博客，这一段讲得比较清楚

这个维护子树信息真的搞不透，有时候维护的东西从哪里取出来都不知道，我还是太菜了

一些套路

LCT能有什么套路

但还是有几个的

  • 能用并查集维护连通性的时候尽量用并查集，因为findroot太慢（只有加边的时候可以用并查集）
  • 对于一些题目，要维护生成树，但是要删边。而LCT维护生成树做不到把非树边代替树边。那么就离线倒过来做，从后往前，时光倒流（形容的很好），就变成只有加边了

好想我就只知道这么多了，我还是太菜了

一些练习题

为了暂时性的用好LCT，于是做了少许题目

大概是从简到难吧（不好排序），一类操作大部分在一起

接下来的题目就有一定难度了

正好30道，还有一些没做

因为省选来了，所以暂时放下（省选很虚啊，我还是太菜了）

从未结束

从此，LCT的学习告一段落

倒计时，大后天

上一篇：zabbix常用术语


下一篇：c语言——知识点