这是一篇关于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,于是做了少许题目
大概是从简到难吧(不好排序),一类操作大部分在一起
- 【刷题】BZOJ 2049 [Sdoi2008]Cave 洞穴勘测(最简单的,模板判联通性)
- 【刷题】洛谷 P3950 部落冲突(化边为点,维护联通性)
- 【刷题】洛谷 P3690 【模板】Link Cut Tree (动态树)(裸题,上模板)
- 【刷题】洛谷 P1501 [国家集训队]Tree II(维护链上信息,练习打lazy标记)
- 【刷题】BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊(有趣的转化,维护链上size)
- 【刷题】BZOJ 2816 [ZJOI2012]网络(暴力处理染色联通块,LCT维护链上最大值)
- 【刷题】BZOJ 1036 [ZJOI2008]树的统计Count(维护sum与max)
- 【刷题】BZOJ 1180 [CROATIAN2009]OTOCI(维护联通性与权值和,还是链)
- 【刷题】BZOJ 2157 旅游(维护链)
- 【刷题】BZOJ 2243 [SDOI2011]染色(高级一点的pushup)
- 【刷题】BZOJ 3626 [LNOI2014]LCA(差分,答案的转化和标记很重要)
- 【刷题】BZOJ 4817 [Sdoi2017]树点涂色(有点恶心的两个数据结构,还有差分)
- 【刷题】BZOJ 2594 [Wc2006]水管局长数据加强版(维护生成树练手题)
- 【刷题】BZOJ 3669 [Noi2014]魔法森林(维护生成树,枚举一维,LCT一维)
- 【刷题】UOJ #274 【清华集训2016】温暖会指引我们前行(其实是维护最大生成树的裸题)
- 【刷题】洛谷 P4234 最小差值生成树(与魔法森林相似)
- 【刷题】BZOJ 1977 [BeiJing2010组队]次小生成树 Tree(新的生成树)
- 【刷题】BZOJ 4998 星球联盟(维护边双的来了)
- 【刷题】BZOJ 1969 [Ahoi2005]LANE 航线规划(边双)
- 【刷题】BZOJ 2959 长跑(还是边双,都很裸,几乎就是一样的)
- 【刷题】COGS 2701 动态树(维护子树信息的练手题)
- 【刷题】BZOJ 4530 [Bjoi2014]大融合(维护子树size)
- 【刷题】UOJ #207 共价大爷游长沙(维护子树异或和,巧妙的思维与构思,膜拜毛爷爷)
接下来的题目就有一定难度了
- 【刷题】BZOJ 3514 Codechef MARCH14 GERALD07加强版(一开始根本不知道有这样的性质)
-
【刷题】洛谷 P3613 睡觉困难综合征(
症?征LCT加上贪心) - 【刷题】BZOJ 4825 [Hnoi2017]单旋(用一种数据结构维护另一种数据结构,性质发现很重要啊)
- 【刷题】BZOJ 4025 二分图(动态图问题来了)
- 【刷题】BZOJ 1453 [Wc]Dface双面棋盘(还是动态图,都要离线)
- 【刷题】BZOJ 4573 [Zjoi2016]大森林(虚点的建立很精髓)
- 【刷题】洛谷 P4319 变化的道路(线段树与LCT)
正好30道,还有一些没做
因为省选来了,所以暂时放下(省选很虚啊,我还是太菜了)
从未结束
从此,LCT的学习告一段落
倒计时,大后天