CF1930H Interactive Mex Tree

Alex_Wei · 2024-02-26 17:26:15 · 题解

CF1930H Interactive Mex Tree

首先考虑怎么通过 \min 算 \mathrm{mex}：因为所有数的权值是 0\sim n - 1 的排列，所以集合的最小的没有出现过的数，就是集合的补集最小值。使用 5 个排列上的区间，恰好覆盖所有 “树去掉一条链” 上的所有点。

设 d = \mathrm{lca}(u, v) 且 \mathrm{dfn}_u < \mathrm{dfn}_v，先考虑 d = u 的情况。按 dfs 的顺序将树铺开在平面上，如下图，则所求区域分为以下部分：

• 进入 u 之前进入的红点；
• 进入 u 之后，进入 v 之前进入的橙点，去掉 u\to v 这条链。等于从 u dfs 到 v 时，对路径上的每个点，在往 v 的方向移动之前遍历的所有子树的并。
• 进入 v 之后进入的蓝点；

红点是 dfs 序的区间 [1, \mathrm{dfn}_u - 1]，蓝点是 [\mathrm{dfn}_v + 1, n]。问题出在橙点，它们的 dfs 序被 u\to v 路径上的黄点分割成很多段，段数为黄点的个数，不能接受。

注意此时只用到了一个排列，那么另一个排列就是用来解决这个问题的。与 dfs 相关的序列，除了 dfs 序（进栈序）以外还有出栈序，即离开结点的顺序。注意到所有橙点均在离开 v 之前离开，于是出栈序的区间 [1, \mathrm{dfe}_v - 1] 可以覆盖所有橙点但不覆盖黄点和绿点，其中 \mathrm{dfe}_i 表示点 i 在出栈序上的位置。

对于 u 是 v 的祖先的情况，询问次数为 3。基于此，容易得出 u, v 没有祖先后代关系的情况的解法。

根据需要被覆盖的点在 dfs 序上形成区间的情况，得到以下五个部分：

• 进入 d 之前进入的红点。用 dfs 序的 [1, \mathrm{dfn}_d - 1] 覆盖。
• 进入 d 之后，进入 u 之前进入的橙点，并去掉 d\to u 这条链。用出栈序的 [1, \mathrm{dfe}_u - 1] 覆盖。
• 进入 u 之后，进入 suc 之前进入的浅蓝点，其中 suc 是 d 在 v 方向上的儿子。用 dfs 序的 [\mathrm{dfn}_u + 1, \mathrm{dfn}_{suc} - 1] 覆盖。
• 进入 suc 之后，进入 v 之前进入的深蓝点，并去掉 d\to v 这条链。用出栈序的 [\mathrm{dfe}_{pre} + 1, \mathrm{dfe}_v - 1] 覆盖，其中 pre 是 d 的 suc 前一个儿子，图中 pre = u。
• 进入 v 之后进入的灰点。用 dfs 序的 [\mathrm{dfn}_v + 1, n] 覆盖。

总共 5 次询问。

时间复杂度 \mathcal{O}((n + q)\log n)。因为 nq\leq 3\times 10 ^ 6，所以暴力也可以通过。代码。