题解：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)\)。

对树进行重链剖分（这是在操作中不会改变的）。定义这棵树的虚实链划分的势能为是虚边的重边数量。
注意到一次 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 都不会证。