题解：P16435 [APIO 2026 中国赛区] 集宝

· · 题解

怎么没人写题解？

Statement

有一棵树，给一个序列，每个元素是一个点的一个邻域，多次询问每次给一个点和一个区间，求从该点开始依次走到区间内的每个邻域所需要的最小步数。

## Sol 你先考虑在序列上的情况。 假设从某个点开始需要依次走过 $[l_1,r_1]$ 和 $[l_2,r_2]$ 两个区间，那么可以发现： - 如果它们有交，那么就等价于「需要走过它们的交」。 - 充分性显然；必要性可以考虑，如果它们互相包含则显然，如果部分相交，那么如果没有经过它们的交，就说明是从第一个区间没有相交的部分直接跳到了第二个区间没有相交的部分，这显然是不可能的。 - 如果它们不交，那么假设不妨 $r_1<l_2$，那么一定等价于「先走到 $r_1$，再走到 $l_2$」。 - 显然不可能存在更短的路径。 那么你考虑维护一个区间的限制，那么只可能有两种情况： - 需要走过一个区间； - 需要从一个点（先走到这个点）然后经过一些步数走到另一个点。 你发现这样的限制是可以任意合并的：第一种和第一种的合并如上；第一种和第二种，显然会从离起点最近的那个点走到起点；第二种和第二种，令前者的终点走到后者的起点，步数加上它们之间的距离即可。 那么直接考虑猫树分治，对于跨过中点的询问预处理出中点向左向右的限制，对每个询问合并起来即可，然后递归下去。 因为要求强制在线，直接把所有信息全都用 $\mathcal O(m\log m)$ 空间预处理出来即可。 再来看树上的情况，你会发现基本上没有任何区别，唯一的额外情况是：两个点的邻域之交可能是一条边的一个邻域。那么你把这种情况也加入后，就会发现所有的六种「两种限制之和」仍然一定是这三种限制之一。 那么就做完了。直接分类讨论实现上述六（或九）种信息合并，然后写一个猫树分治，每次限制合并至多需要 $\mathcal O(1)$ 次求 LCA 或求 $k$ 级祖先，直接使用 $\mathcal O(\log n)$ 的算法即可做到 $\mathcal O(n\log n\log m+q\log n)$。当然如果都写 $\mathcal O(1)$ 的那么就少一个 $\log n$。 笔者赛时使用 $\mathcal O(n\log n) - \mathcal O(1)$ 的 LCA、$\mathcal O(n\log n) - \mathcal O(\log n)$ 的 $k$ 级祖先，以及实现比较粗糙实现的信息合并，在大约 1s 的时间内通过了所有数据，可以发现有很多地方常数是没有看起来那么大的。 其实这题也是完全可以支持单点修改的——把猫树分治换成线段树即可，除了 $q$ 上面会多带一个 $\log m$ 外没有复杂度上的影响。 ## Code 如上所见可以发现本做法的代码实现（尤其是限制合并的部分）可能是一坨史。笔者显然懒得复现赛时代码了。 但是也是有很多简化代码的方法的：比如，涉及边邻域的合并，直接分类讨论可能会非常的复杂，但是通过一些观察，在判掉一些情况后，可以转为点邻域的合并，从而减小代码复杂度。