【总结】Link-Cut Tree

时间:2023-12-15 10:23:44

这是一篇关于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的学习告一段落

倒计时,大后天