主要思路

ZJOI 的题质量都好高啊！真的都是很棒的题。

其实这个覆盖的东西就相当于在 LCT 上进行 Access 时轻重链切换的次数。我们考虑静态的问题，对于点 \(u\) 来说，如果子树内有多个来自不同儿子子树内的子代节点，那么就需要进行合理的分配来把这个轻重链切换次数搞到最大。

转换一下就是两两不同颜色的点进行配对的最大值。设 \(S_0 = a_u, S_i = [\text{第 } i \text{个子树内的 access 次数之和}]\)。那么答案其实就是 \(\max\{ \sum_{i = 0}^m S_i – 1, 2(\sum_{i = 0}^m S_i – \max_{i \in [0, m]} S_i) \}\)，前者是啥都不考虑，后者是连接到一个子节点。后者成为最大值的条件其实就是要成为重儿子。我们考虑维护这个东西。

发现其实我们用贪心的分配方案进行轻重链剖分时，复杂度也是对的。因为被贪心选择的那个子节点确实也是个重儿子，根据树链剖分那一套理论这个复杂度是成立的。

当我们进行修改时，我们就需要用 Access 操作来进行判断和修改。我们需要判断是否存在虚子树中的点成为重儿子，然后进行切换。

Continue reading →