自动搬运

查看原文

来自洛谷，原作者为

	harmis_yz beiribaol，幻想，永恒。

搬运于2025-08-24 23:15:22，当前版本为作者最后更新于2025-03-26 23:03:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面是让求所有深度不大于 $x$ 且不为 $x$ 的 $k$ 倍祖先的点的颜色构成集合的大小。

很显然的，如果一个颜色 $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)$。

那么现在我们有两种做法，一种做法的时间复杂度为 $O(\sum \frac{dep_x}{k}+n\log n)$，一种为 $O(nK)$。最坏情况下，有时间复杂度为 $O(\sum\frac{n}{k}+nK+n\log n)$。看情况平衡即可，时间复杂度 $O(n\log n+n\sqrt{n})$。

然后呢，这题做法肯定不止一个啦，可以暴力求答案，拿个虚树搞。具体的可以自己想，实现应该比上面的那个做法简单很多。