自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 23:01:06，当前版本为作者最后更新于2024-07-15 22:57:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

萌新刚学动态树。

萌新也想在七月二十号之前写完 jabberwockyII，可惜好像做不到了。于是只能来搓模板题。

考虑 LCT。我们在 splay 上维护实链上的信息：保留这段链及其虚子树后，这段链是否全部相同（即连通），链的上下端点，上下端点的颜色/距离，这段链上/下端点所属的极大连通块的直径，上下端点到所属连通块中最远的点的距离，以及如果这段链全部推平为 $0/1$ 之后，上述的答案。

还要维护虚子树的信息。大概是对每种颜色维护每个虚子树上端点所属连通块的直径和连通块中上端点距离的最远距离中的最/次大值。我偷懒用了堆维护，这样是 $O(\log^2n)$ 的。如果用标准的 AAAT，就是 $O(\log n)$ 的。其实直接用静态 top tree 也可以做应该，就是比较难写。

这样就可以切换虚子树，pushup 和推平了。

一份代码实现