虚树构造与终点路径压缩

DFS进入一个子树后，会先走完它再离开。如果两个终点属于某个分叉点的不同孩子子树，按DFS序排列的终点在跨过这条分界时，必有一对相邻终点把这个分叉点作为LCA。于是，无须枚举 $k^2$ 对终点，就能找齐全部必要的会合处。

保留这些会合处以后，其余内部点只是道路上的中途站，可以把一段连续道路折成一条带总长度的边。折叠不能忘记边长，也不能顺手丢掉某个本来就是终点的中途站。

四个终点压成七个点 ​

原树根为0，边及长度为

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,1,3,5,6,4,2,7,8,9,10]$。给定 $S=\{4,5,8,10\}$，排序后是 $[5,4,8,10]$，不是编号顺序。相邻LCA依次为1、0、7；第二次排序得到

栈先压入0、1、5。处理4时，5不是4的祖先，弹出5后栈顶为1，连 $1\to 4$。处理7时，4和1都不再是祖先，弹到0，连 $0\to 7$。之后同样处理8、10。最终边为

例如 $1\to 5$ 代表 $1\to 3\to 5$，长度 $1+2=3$；$0\to 7$ 代表 $0\to 2\to 7$，长度 $3+2=5$。终点之间的最小连通子树总长为 $2+3+4+5+3+3=20$。原树总长21，多出的边 $3-6$ 不连接任何所需终点。

不枚举六条路径也能得到67 ​

对每个虚点 $v$，自底向上算其虚子树内的终点数 $s(v)$。一个点即便不是虚树叶子，只要属于 $S$，也应贡献1。对虚边 $(p,v)$，删除它把 $k$ 个终点分成 $s(v)$ 与 $k-s(v)$ 两侧，恰有 $s(v)(k-s(v))$ 个无序终点对的路径经过它。

所以总和为67。直接核验六个距离得到 $7,14,14,13,13,6$，和仍为67。每对路径上的每条边贡献一次，这就是公式

的双计数证明，不要求所有终点都在叶子上。

三种看似方便的错误 ​

只保留四个终点会漏掉1、0、7这三个会合处，无法把真实路径组织成正确的祖先树。按编号排序而非DFS序，虽偶尔碰巧补齐，也不满足“子树形成连续段”的证明前提。把所有虚边都当长1，则连通子树长度错成6，终点距离也随之改变。

编号排序确实会失败：另取根0、单位边 $0-1,1-2,0-3,1-4$，终点为2、3、4。编号相邻对的LCA都是0，漏掉1；正确的DFS终点顺序是2、4、3，能补出1、0。若把漏掉1的三个终点直接连到0，两条长2的虚边会重复覆盖原边 $0-1$，使子树长度从4错成5，成对距离和从8错成10。

只有 $S=\{4\}$ 时，正确输出是单点4、总长0、成对距离和0。强行加入原根0会多保留从0到4长6的道路，不再是本题的最小连通子树。若任务另要求连接指定基地，应把基地明确加入终点集合后重算。

本算法不能保留被压掉点上的任意附加费用。例如原路径 $1\to 3\to 5$ 上的点3若另有需要计费的标签，单个边长3没有记录它。必须先定义足够的路径摘要，或者把该点也加入保留集。树外额外连边同样会破坏唯一路径与本算法的证明。

为什么相邻LCA已经覆盖所有分叉 ​

取任意两个终点 $x,y$，令 $z=\mathrm{LCA}(x,y)$。若 $z$ 本身是终点，已在 $S$ 中。否则 $x,y$ 位于 $z$ 的不同孩子子树中。在包含终点的这些孩子子树里，取DFS次序相邻的两支；令 $a$ 为前一支中最后一个终点，$b$ 为后一支中第一个终点。

子树前序区间连续，两支之间没有其他含终点的孩子子树，$z$ 自己又不在 $S$，所以 $a,b$ 在全体终点排序中也相邻，并且 $\mathrm{LCA}(a,b)=z$。每个可能的成对LCA因而都会被添加。反过来，所添点本来就是终点对的LCA，没有引入无依据的点。

这些保留点对LCA也封闭：两个保留点若互为祖先，LCA就是其中一个；否则可在它们各自下面选择一个原终点，两终点的LCA与两保留点的LCA相同，也已经加入。因此所有保留点有一个共同的最深祖先，它正是排序后的第一个点。

栈给出最近保留祖先 ​

按前序处理时，栈中的点始终是当前尚未结束的保留祖先链。遇见下一点 $v$，不再包含 $v$ 的子树已经结束，弹出它们不会丢掉 $v$ 的祖先；剩下的栈顶就是此前访问过的最深保留祖先。除第一个点外，栈不会弹空，因为共同根始终是祖先。

每点入栈、出栈各至多一次，边恰连到最近的保留祖先。若一条被压缩的路径内部还存在通向其他终点的真实分叉，这个分叉会是两终点的LCA，本应被保留，与其位于虚边内部矛盾。因此不同虚边在原树上的内部不重叠，它们展开后恰好是连接全部终点的最小连通子树。这里“最小”先指包含意义上的唯一最小子树；零长边允许多个同权扩展，但不改变这个子树本身。

压缩边保留原路径总长，所以所有终点对距离保持；展开虚树得到的子树总长也就是虚边长之和。两个统计量不依赖原根的选择，虽然保留点集和方向可以改变。把主例根改为7，保留点只需 $[7,1,5,4,8,10]$，$7\to 1$ 长7替代经过0的两条边；两项结果仍为20和67。

每次查询的真实费用 ​

本参考器预先用迭代DFS和倍增表，时间与空间为 $O(n\log (n+1))$。若原始列表有 $m$ 项、去重后有 $k$ 项，哈希集合去重的期望工作为 $O(m)$；两次排序为 $O(k\log (k+1))$，相邻的至多 $k-1$ 次倍增LCA为 $O(k\log (n+1))$。栈连接和两项统计都是 $O(k)$。因此一次查询总期望时间为

临时及输出空间为 $O(k+1)$，另加调用者持有的输入列表。代码不为每次查询清空一个长 $n$ 的数组，也不复制全树。若改用常数LCA查询，则可以省去查询界中那一项对数，但必须另付并验证那套预处理，不能直接写成本参考器已经达到 $O(k\log k)$。

上述界按一字可容纳距离、终点计数和总和计。任意精度整数的乘法与加法需另计位成本；打印全部原路径也需按展开边数付费，$O(k)$ 大小的虚树输出不包含免费展开。

共同终点会把终点改成 $\{5,6,10\}$，得到五点虚树、总长14与两两距离和28，并要求解释哪些分叉留下、哪些道路消失。完整参考器打印逐边终点数与贡献，可与直接枚举路径对照。