LCT哲学-个人总结

## 个人理解 LCT其实也是一个暴力的数据结构，可以快速维护链的信息。得益于splay的灵活性，LCT也具有灵活的动态结构。求解的方法非常暴力：makert(x), access(y), splay(y);这时，$x\to y$链上的信息就在y那里了。 由于使用的是splay，所以维护的信息需要能够快速合并。 ## 弹飞绵羊 这道题，是一个精简版lct，而且不能进行makeroot操作，所以很多操作都不太一样，  尤其注意，在断边时，x父亲在x的左子树里，但不一定是左儿子！所以修改时需要$fa[ch[x][0]]=0$不是$fa[y]=0$ 准确的说，y在x的左子树的最右点，如果非要$fa[y]=0$，需要先access(y)，使y会独自在x的子树里。 ## 水管局长 套路：删边变成加边，然后用LCT找到当前最小生成树上的最长边，替换掉。 如何使边权变为点权？为每个边新建一个点即可。 这道题，我最初用了一种把边按时间排序的方法来做，应该是哪个细节写错了，导致挂了。 ### 最小差值生成树 对于生成树，我们难以进行删边操作，比较方便的是加边操作，所以我们每次移动右端点，加入一条边，去掉环上的最小边，左端点跟着动就是答案。 ### 魔法森林 把边按a排序后维护b的最小生成树，注意这道题的自环会RE。 ## 星球联盟 这个单独写一篇。 # LCT维护子树信息 这个也单独写一篇。 ## BZOJ 3514 ~~做这道题的时候，调LCT死循环调傻了...最后发现是会有自环的情况，这个时候一定要特判！~~ N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。**强制在线** 一眼看上去很神仙的题。因为强制在线，总是让人忽略了离线的方法。我们考虑扫描线的思想，对于每个r，维护最大生成树。而树的联通块个数=点数-边数。所以问题就转化为了询问最大生成树上的边，边权在$[l,r]$的数量——我们可以使用主席树！同时，通过可持久化，我们可以很方便的应对强制在线的情况。 ### BZOJ 2555 SAM+LCT维护子树信息。 ### P4721 [USACO18FEB]New Barn 这道题有很多比较水的做法，但是LCT的做法比较值得思考——而且还支持删边。 我们Splay上维护信息$f[i]$表示点i的Splay子树里，深度最小的点到点i的Splay子树（可通过虚边，用可删堆维护轻儿子）的最远点的距离。转移分别讨论从左儿子，右儿子和自己转移即可。注意，因为要支持reverse操作，需要同时维护一个完全相反的标记。