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

yyyx_ · 2026-05-12 09:45:50 · 题解

场外口胡 T1 和 T2 共取得了 \sim65pts，没有人类了。绝望中瞪出了 T3，数据结构好啊。

自然地，将一个点 a_i 视作一个半径为 d_i 圆，把这个圆中的所有点视作 i 颜色点。

引理 I：以 x 为起点，走向离 x 最近的 l 色点 x'，然后 x\gets x'，l\gets l+1（l\le r）。走的总距离即为答案。

证明：给定任意一个合法简单路径，由于在树上，所以一定有一个 c 色点 x' 使得 c-1 色点 x 到 x' 的距离最短。证毕。

于是就得到了一个 \mathcal{O}(n\log n+mq) 的做法（使用 \mathcal{O}(1) LCA）。

注意到 C 性质 l=1，感觉这很差分。发现差分根本做不到：如果令答案为 f(1,r)-f(1,l-1)，那么要求圆 l-1 到圆 l 的最短路交点和查询给定的 x 到圆 l 的最短路交点一致（其实如果保证了圆不重合就可以差分了喵，读者自行思考）。

然后你发现一件事情：哪怕 l=1，也不能直接预处理 f(1,r) 的答案，因为起点和圆 1 的交点可能被后续很多圆也覆盖了，出题人太坏了。我们发现，如果保证了所有圆不重合，那么这就是汤题：本质上是因为在圆 2 上的起点确定，而前面的计算是 \mathcal{O}(1) 的（查询 [l,r] 同理，在圆 l+1 上的起点确定）。

于是我们需要考虑把圆重合这个事情解决。

引理 II：树上两个相交圆（定义和文章开头一样）的交还是一个圆。

证明：设圆心 x,y，d=dis(x,y) 为两圆心距离。在 x 到 y 的唯一简单路径上，一定存在一点 z（可能在边上），满足：

如果结论成立，则有以 z 为圆心的圆，半径为：

此时，z 到 x 的距离为 r_1-R，到 y 的距离为 r_2-R。

必要性：交集内的点都在圆 (z, R) 内。

设点 u 是交集内的任意一点，即满足 dis(u,x)\le r_1 且 dis(u, y)\le r_2。点 u 到路径 x\to y 有唯一的最近点，设为 v。则有：

由于 z 和 v 都在路径 x\to y 上，对于路径上的任意点 v，都有：

通过圆 x,y 得：

把他们带进 dis(u,z)=dis(u,v)+dis(v,z)：

化简一下：

充分性：圆 (z, R) 内的点都在交集内。

设点 u 满足 dis(u,z)\le R。我们需要证明它同时满足到 x 和 y 的距离约束。

对圆 x 有：

代入 dis(u,z)\le R：

根据 z 的构造，R+dis(z,x)=r_1：

即点 u 在圆 x 内。对于圆 y 同理。

由于 dis(u,z)\le R 是点 u 属于两圆交集的充要条件，因此两圆的交集构成了以 z 为圆心、R 为半径的圆。证毕。

考虑如果我们要依次经过 k,k+1 色圆，一般化地考虑起点 x 三种情况：

1. 本身就在交上，不动；
2. 在 k 上，到交圆最短等价到 k + 1 最短；
3. 在 k+1 上，到交圆最短等价最小代价达到 1 情况。

那么直接到他们的交圆上是不劣的。所以我们就可以做区间合并了！把相离或相切的圆直接算距离，然后变成两个半径为 0 的点进行维护；否则直接合并圆。查询的时候让起点直接合并进去即可。

直接上 \mathcal{O}(1) LCA 和 \mathcal{O}(1) k 级祖先，合并就是超大常数 \mathcal{O}(1)，于是套上线段树时间复杂度就是 \mathcal{O}((m+q)\log m) 的。感觉超级好写。