CF1930H 题解

sunkuangzheng · 2024-02-18 17:46:52 · 题解

题目链接。

• 给你一棵 n 个点的树，每个点的点权 \{a_i\} 是 0 \sim n - 1 的排列，q 次询问，每次查询 u \to v 的路径 \operatorname{MEX}。

• 排列是交互库隐藏的且每次询问的排列 a 不同。你可以在所有 q 次询问开始前构造两个 1\sim n 排列 p_1,p_2，每次向交互库给出 t,l,r，得到 \min \limits_{i=l}^r \{a_{p_{t,i}}\} 的值。只有 5 次询问机会。

首先对于排列 a，有结论：子序列 a' 的 \operatorname{MEX} 等于其补集 b 的 \min，证明显然。那么我们就有做法：对原树进行重链剖分，则 u \to v 的路径会被拆成 \mathcal O(\log n) 段连续 dfn 区间，则这些区间的补集也是 \mathcal O(\log n) 段 dfn 区间，令 p_1 为 dfn 数组，则暴力问出这些区间 \min 然后取 \min。这也就是题面中提到的 HLD 解法，遗憾的是我们只有 5 次询问机会。

我们发现上述解法完全没有用到排列 p_2，没有充分利用条件。解决这道题最关键的地方是想到欧拉序。令 p_1 为 dfs 序的排列（也即欧拉序的 in），p_2 为欧拉序的 out 的排列（离开 u 子树时将 u 计入数组）。

考虑怎么利用这两个排列计算 \min。以下令 dfn_u < dfn_v。

核心性质是：对于 u，其祖先的 dfn 小于其 dfn，而 out 大于其 out，我们可以用这些性质去除链上的节点。

• 情况 1：u 是 v 的祖先。

此时 out_v \le out_u，对于任意 i 满足 dfn_i < dfn_u 或 dfn_i > dfn_v，i 一定不在 u \to v 的链上；同理，对于 i 满足 out_i < out_v，i 也一定不在 u \to v 的链上。

我们可以发现所有不在链上的点全都已经被去除。这个是显然的：对于非 v 祖先 i，如果 i 在 v 以前遍历，则 out_i < out_v；如果 i 在 v 以后遍历，则 dfn_i > dfn_v。当然记得判掉 i 在 1 \sim u 的链上。

• 情况 2：u,v 没有祖先关系。

此时不在链上的点有五种类型，对应的 dfn 或 out 见下图（dfs 顺序从左到右）。

（PS：下图左侧部分应为 out 而不是 dfn，但是图做好懒得修了 /kk）