重心分解与最近标记点

删除重心会把道路网络分成几支。若查询点和某个服务点在不同支，它们的唯一路径必须经过这个重心；若还在同一支，就继续到下一层。最终总会遇到一个恰好位于两点真实路径上的共同分隔点。

其他祖先可能让路线绕远。例如从同一支的两个点先绕到顶层重心再回来，会重复走一段路。非负边长使这种绕路不会比真实路径更短，所以可以把所有候选取最小：绕远者不会造成低估，而其中至少一个候选不绕远。

十一个顶点，三次开放 ​

固定以下原树，括号内为边长：

0—1(2)  0—2(3)  1—3(1)  1—4(4)  3—5(2)
3—6(1)  2—7(2)  7—8(3)  7—9(1)  9—10(2)

删除0后两支各有5点，所以先选0。左支重心为3，删除后大小为2、1、1；右支重心为7，删除后大小为1、1、2。两点分量按编号平局选1或9。最终分解父亲为

0:无；1:3；2:7；3:0；4:1；5:3；6:3；7:0；8:7；9:7；10:9

第一次标记4。它的标签是 $(0,6),(3,5),(1,4),(4,0)$。查询6时，自己的标签为 $(0,4),(3,1),(6,0)$：

答案为6，真实路径是 $6\to 3\to 1\to 4$，长度 $1+1+4=6$。顶层候选10多走了 $1\to 0\to 1$，不能只查顶层摘要。

接着标记8，查询10。经0的候选为 $8+6=14$，经7为 $3+3=6$，经9和10没有标记摘要。最近点为8，路径 $10\to 9\to 7\to 8$ 长 $2+1+3=6$。最后标记6，再查询5，经0的候选为 $5+4=9$，经3为 $2+1=3$；最近点变为6。三次答案依次为6、6、3，不是只对一份静态标记集合求值。

三个不能偷偷扩大的条件 ​

负边会破坏下界。 在路径 $0-1-2$ 上把两边长度设为 $-2,1$，重心为1，只标记0并查询0。经1的候选是 $-2+(-2)=-4$，却小于自身的真实简单路径距离0。因此本参考器在入口拒绝负边；“树上没有圈”不能挽救这次绕路比较。

取最小不能撤销。 若只标记4后又把4取消，旧 $B$ 仍保存4提供的距离，查询会回答一个已经不存在的点。支持删除需要保存更多候选，例如具有删除能力的有序多重集合，并重新计费。不能把 marked[4] 改为假就声称实现了删除。

分解静态，标记动态。 改变边长会使距离标签失效；link/cut还会改变分量与分隔关系。本接口必须重建。与重链剖分理路重链剖分heavy-light decomposition · HLD按子树大小选择重儿子，把树路径拆成对数条连续链区间。不同，这里没有把任意路径变成若干连续数组区间；与Link–Cut Tree理路Link–Cut TreeLink-cut tree以 preferred-path 分解和辅助伸展树维护动态森林，在对数摊还时间内支持换根、连边、断边与路径聚合。也不同，它不承诺维护动态森林。

为什么最小候选恰好是答案 ​

设标记集合为 $M\ne \varnothing$，真实答案 $D=\underset{v\in M}{min}d(u,v)$。先证明算法不会低估。一个有限的 $B[c]$ 由某个真实标记点 $v$ 达到，所以相应候选为 $d(u,c)+d(c,v)$。原树上这段拼接行走比唯一路径可能多走往返边，但非负长度保证

再取真正最近的标记点 $v^{\ast }$。让 $c$ 是 $u,v^{\ast }$ 在分解树上的最近公共祖先。若 $c$ 等于其中一点，它显然在原路径上；否则两点在删除 $c$ 后进入不同分量，原路径也必须经过 $c$。二者标签都含 $c$，且 $B[c]\le d(c,v^{\ast })$，于是

上下两向给出相等。这里的分解树LCA只用于证明，查询程序不必真的求它；逐一检查短标签已经覆盖这个见证。返回的标记身份也是真实最近点：若其经 $c$ 的候选等于 $D$，它的真实距离夹在 $D$ 与该候选之间，只能同为 $D$。

构建、操作与输出分别花多少钱 ​

每层剩余分量至多减半，任一顶点最多出现在 $1+\lfloor {\log }_{2}n\rfloor$ 层。因此标签总数为 $O(n\log (n+1))$，标记与查询都至多检查这一条对数长祖先链。固定字长距离、数组访问及整数运算下，完成标签后每次操作最坏 $O(\log (n+1))$，$B$ 和标记数组另占 $O(n)$。

构建采用分治法理路分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。，逐分量重新求子树大小并填写距离标签。每层各分量的顶点不相交，总遍历工作为 $O(n)$，层数对数，故总时间和标签空间为 $O(n\log (n+1))$。参考器保留原邻接表并跳过已删除点；即使小分量仍会检查通向旧重心的邻接项，同一层所有被访问顶点的原度数总和仍不超过 $2(n-1)$，因此这些检查也被上述总界覆盖。输入连通性、边数和权值检查为 $O(n)$。

参考器用字典记录一个临时分量的父亲和大小，这部分采用期望常数散列表操作；构建的相应界为期望 $O(n\log (n+1))$。标签建好后的 mark/nearest仅访问列表，仍有上述最坏界。若整数可任意长，应再乘实际加法与比较的位成本。输出全部标签本身已可能需要 $\mathrm{\Theta }(n\log n)$ 项；只构造分解树另有线性算法，[1]并不意味着本页带全距离标签的输出也能无条件线性完成。

程序用显式栈遍历原树，长链不会用掉同样深度的宿主递归栈。全点对距离、全部标记集合和故障输入检查是测试工具，不属于单次在线查询的费用。

共同终点要求交出每层分量大小、三个查询的所有候选及真实路径。完整参考器还用同一原树构造虚树理路虚树构造与终点路径压缩Virtual tree construction · Compressed terminal tree · 虚树将查询终点按DFS序排序，补相邻LCA并以栈连接最近保留祖先，在至多2k−1点的压缩树上计算连通子树与两两距离总和。：后者按一次查询的少数终点压缩道路，本页则预先给每个顶点保存分隔点标签，两种缩小工作量的方法有不同接口。