题解：P14623 [2018 KAIST RUN Fall] Coloring Roads

· · 题解

题意即为：给定一棵有根树，维护以下两种操作：

  1. 将点 x 到根路径上所有边颜色改为 c；
  2. 查询出现 k 次的颜色种数。

考虑维护同色树上连续段。具体地，当修改 x 到根的路径时，将 x 到根上的所有点从它们原来所在的连续段断开，并将这些点缩成一个新的连续段。

不难发现这就是 LCT 的 access 操作，直接 LCT 维护即可做到 \mathcal O(Q\log n)。

下面证明一下 LCT 的 access 操作中虚实边切换次数均摊是 \mathcal O(\log n) 的，即上面过程中连续段改变次数是均摊 \mathcal O(\log n)。

:::info[证明]{open} 对树进行重链剖分（这是在操作中不会改变的）。定义这棵树的虚实链划分的势能为是虚边的重边数量。 注意到一次 access 中虚实边切换次数不超过操作的点到根的路径上虚边数量的两倍。考虑这些虚边的轻重性：

  1. 如果是重边，那么遇到一条这样的边时就会使势能减一，所以这部分复杂度可以摊到势能中；
  2. 如果是轻边，由重剖性质，每次操作只会遇到 \mathcal O(\log n) 条，每条都至多使势能加一（这条轻边变成实边导致一条兄弟重边变成虚边）。

初始时势能即为重边数量 \mathcal O(\log n)，势能总增加量 \mathcal O(Q\log n)，故第一种情况次数均摊 \mathcal O(\log n)，第二种情况次数严格 \mathcal O(\log n)。 :::

所以也可以用重链剖分加数据结构维护连续段做到 \mathcal O(\log^2 n)，或者用 Treap 等平衡树实现 LCT 的操作也是这个复杂度。

至于为什么 LCT 是单 \log 我不会证，我连 splay 都不会证。