LCT 练习记录
点击量：266
LCT的题目难度从模板到各种神奇科技有很多级别。
LCT的代码确实好写，不过细节需要特别注意。初学的时候还是背着吧
题目来源
感谢这位老鸽的题单。
感谢学习笔记非常详细，并热心解答我疑问的FlashHu。
感谢YangZhe的论文。
模板
模板
洛谷 P3690 【模板】Link Cut Tree （动态树）
LCT的所有基础操作，注意是基础。
维护并查集
LCT可以当作一个可以删边的并查集，也就是维护一棵树的连通性，比较好写，甚至不用makeroot。
洛谷 P2147 [SDOI2008]洞穴勘测
直接维护就可以了，保证：“删掉的边存在；任意时刻任意两个洞穴之间至多只有一条路径。”减少了很多难度。
洛谷 P3950 部落冲突
和上面那题一样，只是存边不太好存。
维护生成树
一般要查询路径上最大值或最小值的题目需要维护生成树这个贪心来解决。
洛谷 P4172 [WC2006]水管局长
倒序处理所有操作，构造生成树并维护生成树即可。
这里要注意的是边有边权，详细处理方法写在题解里了。
当要连接$ (u,v,w)$时，先split(u,v)，查询这条链上有没有比$ w$更大的边，如果没有就不连，如果有，删掉最大的边再连接。
洛谷 P2387 [NOI2014]魔法森林
需要想到正确的枚举方法。
因为这个题还是和链上最大值有关，当有两个关键字时，可以考虑把其中一个关键字先排序，然后按这个顺序枚举边，维护生成树。
比如说以$ a$为关键字排序，就可以找到在$ a_{i\max}$为任意存在值时，生成树$ b$的最小值。
todo:
- 写一篇题解
洛谷 P4234 最小差值生成树
生成树题做多了就能一眼看出来了。但是不知道是lct的话还得想想。
QTREE 系列
QTREE
这个鬼题在luogu上只能用C语言交。以前写的树剖懒得改成C语言了，但是lct没用什么stl就很好改了。
C语言注意事项
我是学了一波C语言吧
- 头文件
<c*>要变成<*.h>。例如<cstdio>-><stdio.h>，剩下的不是c开头的基本不能用，因为都是C++里面才出现的。- C语言中没有
bool类型……直接用int代替算了。- 我的码风比较偏C就没有特别多需要改的了……
QTREE1
是luogu版本的，没有多组数据。lct裸题。
QTREE2
主要是求链上第$ k$个点。分离出来链后，一定满足点-边-点-……-点-边-点这种结构。我们要查找第$ k$大元素，就要访问split(u,v)后splay中第$ 2k-1$大的元素。
注意访问（dfs）的时候要pushdown，不然左右关键字大小会错。
todo：
- 写一篇题解
维护双连通分量
bzoj 4998 星球联盟
学了一下lct维护双连通分量，用了一堆并查集，样例调了快一个小时。样例过了居然1A了……运气还不错吧。以后还要找题练习。
代码也有待改进。
todo
- 写一篇题解
其他
洛谷 P3203 [HNOI2010]弹飞绵羊
不用换根的lct，感觉是个阉割版，一开始还没敢写。
SPOJ 8791 DYNALCA – Dynamic LCA
lct上求有根树的lca，比较有趣的解法。因为有根，所以不能 makeroot。
有一种很简单的方法，对于 $ \operatorname{lca}(x,y)$，先对 $ x$ 进行 access 操作。此时 $ x$ 一定在根节点所在的 splay 中。而且 $x$ 是 splay 中最深的节点，因此我们 access(y) ，看它在哪一步被并到根节点的 splay 中去，也就是循环中的 $ y$ 的最终值。
说点什么