题解：P10776 BZOJ3914 Jabby's shadows

· · 题解

萌新刚学动态树。

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

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

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

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

一份代码实现