P16435 [APIO 2026 中国赛区] 集宝

Genius_Star · 2026-05-12 12:12:00 · 题解

思路：

令 S_i 表示第 i 颗宝石的邻域集合。

对于一次询问，考虑依次维护当前所有可能的可达点的集合，初始是 S_l，要走到下一个点的邻域内，那么可达点的集合会变为 S_l \cap S_{l + 1}，以此类推，最后可达点的集合是 S_l \cap S_{l + 1} \cap \cdots \cap S_r。

显然这样是有问题的，如果中间某个时刻是空集了怎么办？即若走到一个点 k 使得 S_l \cap \cdots S_k \ne \emptyset, S_l \cap \cdots S_k \cap S_{k + 1} = \emptyset。

容易发现，令 T = S_l \cap \cdots S_k，那么在收集第 k + 1 个宝石时，所有 T 中的节点在贪心往 S_{k + 1} 中移动后一定都会在落一个点上。

这是因为若干邻域交一定是联通块，这是显然的，而一个联通块都往一个点贪心的蠕动，最后肯定是全部都到这个点邻域边界的某个点处，简单分讨一下即可证明。

还有一个性质，在从 x 出发时，到达某个 T 的点走的一定是简单路径，考虑归纳证明：

• 设当前收集了第 r' 个宝石在位置 p，现在要收集第 r' + 1 个宝石。

• 若选手从来没有动过，即它一直在 S_l, \cdots, S_{r'} 集合中，现在往 S_{r' + 1} 动的路肯定是简单路径。

• 否则选手动过，找到它上次动的时刻 t，那么它所在位置 p 一定是恰好在某个点 u 的邻域边界上，根据归纳到达 p 走的是简单路径且一定不会经过 S_u 中的点；接下来反证法一下，如果 p 往回向点 v 走了，因为邻域交一定非空，那么 v 的邻域 S_{r' + 1} 一定包括了 p（因为 p 是在上一个邻域交的边界上），所以 p 不会动，与 p 往回走矛盾。

所以你可以发现，对于一次询问，它一定是走一条简单路径，然后接下来一直从某个点开始跳跳跳。

那么这题的做法就呼之欲出了，设 f(x, l, r) 表示从 x 出发收集 l \sim r 宝石的最短路径。

对于每个 l，求最远的 k 使得 S_l \cap \cdots S_k \ne \emptyset，令 T = S_l \cap \cdots S_k，若 x \in T，那么 x 不用动；否则 x 动过，最后一定在 T 的边界上，且又是简单路径，于是可以分讨一下 x 在 T 子树内或者外面，可以倍增跳或者是到达 T 中的根。

若现在选手在 p，容易求出其到 S_{k + 1} 后的点 p'，那么我们要求的是 f(p, k + 1, r)；可以看作是 f(1, 1, r) - f(1, 1, k + 1) + dis(p, p')，这是因为即使从 1 出发，收集 k + 1 时也一定在 p' 这个点，于是可以直接差分。

于是我们只需要求 f(1, 1, i)，直接模拟一遍即可。

现在问题转化为求区间邻域交了，这个咋做？考虑比上面更强的结论，树上邻域交，不仅是一个联通块，还是一个树上邻域，其中心在其中间某个点或者某条边的中点取到。

为了方便处理，可以在边中间插入一个点，这样两个邻域合并后的邻域中心也在点上；发现这个性质后，求区间邻域交，就比较简单了，考虑用线段树维护，只需要支持快速合并两个邻域成新的邻域了（或者无交）：

• 设合并 (u, d_1), (v, d_2) 这两个邻域。

• 若 dis(u, v) > d_1 + d_2，则无交，是空集。

• 否则找到 u \to v 链上距离 u 为 d_1 的点 u'，距离 v 为 d_2 的点 v'，那么合并出的邻域中心在 u' \to v' 链的中点处，分讨一下即可，只需要支持求树上 k 级祖先。

求最远的 k 使得区间邻域交非空可以直接在线段树上二分解决；这样常数有点大，可以考虑倒着走不删除指针做到 O(m \log n)。

总时间复杂度为 O((m + q) \log n \log m)；可能会被卡常，但是因为没有修改，可以直接上猫树，做到 O(m \log n \log m + q \log n)。