题意即为：给定一棵有根树，维护以下两种操作：
- 将点 \(x\) 到根路径上所有边颜色改为 \(c\)；
- 查询出现 \(k\) 次的颜色种数。
考虑维护同色树上连续段。具体地，当修改 \(x\) 到根的路径时，将 \(x\) 到根上的所有点从它们原来所在的连续段断开，并将这些点缩成一个新的连续段。
不难发现这就是 LCT 的 access 操作，直接 LCT 维护即可做到 \(\mathcal O(Q\log n)\)。
下面证明一下 LCT 的 access 操作中虚实边切换次数均摊是 \(\mathcal O(\log n)\) 的，即上面过程中连续段改变次数是均摊 \(\mathcal O(\log n)\)。
对树进行重链剖分（这是在操作中不会改变的）。定义这棵树的虚实链划分的势能为是虚边的重边数量。
注意到一次 access 中虚实边切换次数不超过操作的点到根的路径上虚边数量的两倍。考虑这些虚边的轻重性：
- 如果是重边，那么遇到一条这样的边时就会使势能减一，所以这部分复杂度可以摊到势能中；
- 如果是轻边，由重剖性质，每次操作只会遇到 \(\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 都不会证。