沿少量树信息路线，完成重心分解的只增标记查询理路重心分解与最近标记点Centroid decomposition · Centroid tree · 点分治反复删除使剩余分量至多减半的顶点，保存原树距离标签，用对数条分隔点记录精确回答只增标记的最近点查询。与虚树的终点压缩理路虚树构造与终点路径压缩Virtual tree construction · Compressed terminal tree · 虚树将查询终点按DFS序排序，补相邻LCA并以栈连接最近保留祖先，在至多2k−1点的压缩树上计算连通子树与两两距离总和。。前者预存每点的短标签，后者按一次查询临时保留少数道路。最终应交付可复算的中间记录，不能只报三个最短距离和一个总和。

下载完整标准库参考器，运行 python algorithms-small-tree-queries-check.py，把标准输出保存为JSON。程序不读写其他文件；python -O也会执行显式检查。输出先给本页各项记录，再给穷举、随机、长链和非法输入的检查数量。附带诊断遍历不是在线查询的一部分。

一、固定原树，另外建立分解树 ​

顶点为0到10。按以下顺序加入无向边，三元组为 (端点,端点,长度)：

(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为原树根时，DFS前序必须为 [0,1,3,5,6,4,2,7,8,9,10]。这份根和前序服务于虚树；重心分解另有自己的父亲数组。重心候选并列时取编号较小者。

提交每个重心删除前的分量大小及删除后的所有大小。前三个主要分量为：重心0对应 11 → 5+5；重心3对应 5 → 2+1+1；重心7对应 5 → 1+1+2。每份记录都要满足“剩余大小总和等于原大小减一，且每项不超过一半”。最终分解父亲数组为

[None,3,7,0,1,3,3,0,7,7,9]

再交出全部顶点的 (重心祖先,原树距离) 标签。尤其核对4的 [(0,6),(3,5),(1,4),(4,0)] 与6的 [(0,4),(3,1),(6,0)]。若你从分解树边数计算距离，这两份记录会立即暴露问题。

二、逐次开放服务点，保留全部候选 ​

初始查询6，应返回 None。之后依次做以下三轮，不能在每轮前清空已有标记：

同时提交三条原树路径：6–3–1–4、10–9–7–8、5–3–6，逐边加和。解释第一轮经0为何多付4：它把 1–0–1 往返算了一遍，而经3不绕路。

再次标记6必须返回“未改变”；随后查询0的距离为4，最近标记为6。证明中要分别说明候选不会低于真实最近距离，以及为什么至少有一层恰好在真实路径上。零长度导致平局时，参考器返回编号较小的最近标记，不能把距离0等同于顶点相同。

三、把四个终点变成六条带权虚边 ​

另开一次与标记状态无关的终点查询，输入列表 [4,5,8,10]。提交排序后的终点 [5,4,8,10]，相邻LCA [1,0,7]，以及最终保留点 [0,1,5,4,7,8,10]。

逐步写出栈。处理4时应从 [0,1,5] 弹去5；处理7时从 [0,1,4] 弹去4、1。最后六条虚边及长度为

(0,1,2) (1,5,3) (1,4,4) (0,7,5) (7,8,3) (7,10,3)

把每条虚边展开成原路径，核对内部不重叠。长度和是20；原树总长21，未用的一条边是 3–6。这里虚边 0–7 长5，而不是原树里真的有一条长5的直接边。

四、按切开的终点对计费 ​

沿上面六条边的顺序，交出下侧终点数 [2,1,1,2,1,1]、跨边无序对数 [4,3,3,4,3,3] 和距离贡献 [8,9,12,20,9,9]。总和为67。

独立枚举六个无序终点对。按 (4,5),(4,8),(4,10),(5,8),(5,10),(8,10) 的顺序，距离是 [7,14,14,13,13,6]。将两份记录逐项解释为同一批“路径经过边”的不同求和顺序，而非仅检查两个和相等。

再用终点 [1,5] 检查内部终点：虚根1本身也贡献一个终点，唯一虚边长3，下侧计数1，成对距离和3。只给叶子计数的程序会错误地把这一对漏掉。

五、改变终点与原根，保留应当不变的量 ​

将终点改为 [5,6,10]。正确保留点是 [0,3,5,6,10]，边为

(0,3,3) (3,5,2) (3,6,1) (0,10,8)

总长14，下侧终点数 [2,1,1,1]，逐边距离贡献 [6,4,2,16]，总和28。说明1、7、9为什么此时只在压缩道路内部，3为什么必须留下。

回到原四终点，把原树根改为7并重新做DFS与倍增预处理。保留点应为 [7,1,5,4,8,10]；从7到1长7，接着1到5长3、1到4长4、7到8长3、7到10长3。保留点与方向改变，最小连通子树总长和两两距离和仍为20、67。

最后分别输入空列表与 [4,4,4]：前者为空树，后者只有点4；两项统计都为0。重复项不增加终点权重，单点查询也不自动连接原根。

六、用反例划清接口与成本 ​

另建五点单位边树 0–1,1–2,0–3,1–4，原根0，终点2、3、4。按编号排序会只添加LCA 0，漏掉1，进而把子树长4错算为5、距离和8错算为10。按DFS终点序2、4、3重做，解释连续子树区间在哪一步恢复了证明。

在三点路径 0–1–2 上若边长为−2、1，重心1会给“标记0、查询0”产生−4的绕路候选。说明非负条件为什么必需，并记录入口拒绝负边；不能为了展示错误答案而让正式查询器接受这种输入。

只标记4后“取消4”会使旧最小值仍在；本接口没有单点取消，清空全部状态用 reset 并支付 $O(n)$。把主例边 1–4 从4改为10，也不能继续用旧标签：仅标记4时，查询6应从6变成12，需要重新构建。检查调用者修改原始边列表不影响已构造对象，非法顶点不会先写入标记状态。

结尾分别核算：参考器重心预处理因临时字典而采用期望 $O(n\log (n+1))$ 时间，静态DFS与倍增表的构建为最坏 $O(n\log (n+1))$；两套索引空间均为 $O(n\log (n+1))$。重心接口每次最坏 $O(\log (n+1))$，虚树对长度为 $m$、去重后含 $k$ 点的输入采用期望 $O(m+k\log (k+1)+k\log (n+1)+1)$。说明散列表、倍增LCA、任意精度整数和展开全部原路径各在账单哪里出现。若每次先清空长 $n$ 的数组，就已经改变了这里的查询界。