很显然的，如果一个颜色 col 在最后的集合中没有出现过，那么 c_i=col 的 i 要么是 x 的 k 倍祖先，要么深度大于 x 的深度。因为没被删的点看起来很不好维护，所以考虑维护有多少种颜色完全被删了。
考虑将深度大于 x 的深度的点和 x 的 k 倍祖先分开维护。对于深度大于 x 的深度的点，我们可以再反一次，转化为深度不大于 x 的深度的点的颜色构成集合的大小。求这个有若干种方式，能过在 O(n) 的复杂度维护出所有 dep_x=y 时的答案。那么现在问题转化为：求有多少种颜色 col，满足 c_i =col \land dep_i \le dep_x 的点均为 x 的 k 倍祖先。这个很典吧，考虑根号分治。
由于 x 的 k 倍祖先数量为 \lfloor\frac{dep_x}{k}\rfloor，如果我们每次暴力跳 k 级祖先，那么复杂度是 O(\frac{dep_x}{k}) 的。维护一个颜色是否出现完可以按照 BFS 序记录每个点。那么记 lst_i 为颜色 i 上一次出现的位置，则 dep \in [dep_u,dep_{lst_i}] 颜色 i 不能出现 >2 次，即将每种颜色按照 BFS 序排序后它们相邻。所以单次时间复杂度是 O(\frac{dep_x}{k} \log n)\sim O(\frac{dep_x}{k})。
如果这个 k 极小，上面的做法显然很裂。考虑枚举 k，将所有 k 相同的询问统一处理。假设现在 k 一定。对于一个颜色 col，我们将 c_i=col 的点剖出来，建成一棵虚树，观察虚树的形态。我们将虚树按照深度分层，那么对于前 i 层，如果我们有一个询问 Dep_{i+1} >dep_x\ge Dep_i，则当 col 会对 x 产生贡献的必要条件一定是前 i 层的虚树形态是一条链。这个显然吧，如果不是链，那么一定有一个点 u，有 deg_u \ge 3 且 dep_u \le dep_x。那么一定存在一个点颜色为 col 且不为 x 的 k 倍祖先。
我们接着去枚举层数 i。当前 i 层构成虚树的形态为一条链时，考虑会对哪些 x 产生贡献。如果 col 对 x 产生了贡献，那么另一个充分必要条件是这条链上所有点均为 x 的 k 倍祖先。根据虚树的性质，既然是一条链，那么这虚树上所有点的颜色都为 col，所以是必须的。我们有：Dep_i \le dep_x < Dep_{i+1}。哦我是不是忘说了，Dep_i 表示第 i 层节点在原树上的深度。
我们可以找到第 i 层的虚树上节点在原树上的位置。那么现在就相当于对于一个子树的一个深度区间加问题了。哦这里还有个条件，就是 dep_x 应该与 Dep_1 对于 k 同余，且 Dep_j (j \le i) 也应该与 Dep_1 对于 k 同余。维护这个可以将所有颜色合在一起处理，在节点上打 tag 即可。对于一个 k 的时间复杂度 O(n)。