LCT 总结。
前言
久等了！历经了不知道多少天的努力，终于写完辣！这里是题目总结。
题目
P3690 【模板】动态树（Link Cut Tree）
- 维护 数组为一条重链中某个点的子树的异或和，修改的时候直接修改存放每个点值的 数组，求到根的路径的时候依次 ，， ，最后输出 即可。
P2147 [SDOI2008] 洞穴勘测
- 这里需要用到的并查集需要资瓷撤销功能，应当使用按秩合并的并查集+线段树，有点麻烦。单纯只使用普通的并查集可能会使得查询一次的复杂度退化到 。
- 既然都写了 LCT 了，考虑使用 LCT 判断联通。使用 函数。
具体点， 函数将会依次执行： ， ，下传标记， 。先把 到根的路径扒出来，下传信息。下传标记的时候不断的走左儿子走到的深度最小的那个点，就是根。最后讲根旋转上去，维护复杂度即可。
P3203 [HNOI2010]弹飞绵羊
- 因为不存在对一条路径的修改和查询操作，所以不需要换根。相对应的根据题目特性更改 ， 和 操作。
- ， 后， 的子树上的所有点恰好就是 到原来根的路径，因此直接输入 即可， 对应的是新增的弹飞后的节点 。
P1501 [国家集训队]Tree II
- 对于将一条路径上的点权全部 或 的问题，在扒出这条路径之后将整条路径打上懒标记即可。维护几个数组 （点的权值）， （点的重子树的权值和）， （点的重子树的子树大小），（一个 中的加发懒标记）， （一个 中的乘法懒标记）。具体维护方法很像线段树2。
P2387 [NOI2014] 魔法森林
- 最小生成树。直接求解比较麻烦。考虑先让 有序，再动态加上 的最小生成树。具体点，如果当前加上这条边会变成一个环，那么考虑断掉环上最长的边，再加入这条边。这个过程用 LCT 来维护是比较优秀的。
- 题解里面有一句话写的比较迷惑：“当然前提是这条边的 大于环上最大 “，这句话没看懂也不要纠结了，并不影响思考。前面两个分类讨论应该也很到位了。
- 这里有边权了，考虑将边权变为点，即 ， ，当然 要转换到对应的点上咯。
P3703 [SDOI2017]树点涂色
- 路径染色，到根的颜色，比较显然的可以看出可以用 LCT ，颜色就是虚边数量。由于题目和原树的关联实在是有点小大，而且原树确实就是一颗很漂亮的树，所以没必要换根。根据 LCT 的性质， 也直接在 的子数里找一个深度最小的点就行。虚边数量可以在 的时候更新。
P4299 首都
- 动态维护一棵树的重心板子题。两棵树相连重心一定在两颗树的重心的连线上。考虑利用这个性质，有点类似二分的方法在这条链上找重心。（找重心的时候只会往重儿子走）。这里维护了两个子树大小，一个是总子树大小 ，一个是虚子树大小 。
- 记住这里的 和 ，后面的题很有用。
P4219 [BJOI2014]大融合
- 维护子树信息。学会了 和 ，这道题就是一个十分钟秒的屑。 计算答案， ，前面记得先 出来。
P4172 [WC2006]水管局长
- 思路很简单，倒着加边，跑最小生成树。第一篇题解的代码可能会比较亲民，我参考的是 Flash_hu 神仙的代码，貌似有点难理解。依然是将边权变为点，边权极为点权。判联通由于不需要资瓷撤销操作， 或者并查集都行。
后记
Treap 党学 LCT ，先滚去学习了 Splay 才有勇气滚回来的。
LCT 的题目和网络流一样主要都是转化问题。
感谢以下大佬博客的指导：
