考虑树上任意 $k$ 个点 $a_1,a_2\cdots a_k$,包含他们的最小连通子树的边树(也即他们的虚树边权和)可以用如下方式求出:
考虑将 $k$ 个点按照 dfn 序从小到大排列为 $p_1,p_2\cdots p_k$,特别的,钦定 $p_{k+1}=p_1$,则虚树边权和等于 $\frac{\sum_{i=1}^k \text{dist}(p_i,p_{i+1})}{2}$,其中 $\text{dist}(i,j)$ 表示树上 $i,j$ 两点最短路径的边数。
考虑树上任意 $k$ 个点 $a_1,a_2\cdots a_k$,包含他们的最小连通子树的边树(也即他们的虚树边权和)可以用如下方式求出:
考虑将 $k$ 个点按照 dfn 序从小到大排列为 $p_1,p_2\cdots p_k$,特别的,钦定 $p_{k+1}=p_1$,则虚树边权和等于 $\frac{\sum_{i=1}^k \text{dist}(p_i,p_{i+1})}{2}$,其中 $\text{dist}(i,j)$ 表示树上 $i,j$ 两点最短路径的边数。