解题思路
题目中的空间站和航道构成一棵树。可以修建的新航道等价于：对于任意一个空间站 w，若存在两条原始航道 (u,w) 和 (w,v)，则可以在 u 和 v 之间修建新航道。也就是说，所有距离恰好为 2 的空间站对均可以修建直达航道。管理部门可以自由选择部分或全部这样的候选航道进行修建，目标是使 ∑i=1n∑j=1nd(i,j) 最小。
我们把所有可能的新航道按照形态分为两类：
- 横向新航道：连接某个空间站的两个不同子节点，即“兄弟节点”之间的航道。
- 纵向新航道：连接一个空间站与其父节点的父节点，即“祖孙节点”之间的航道（中间经过一个空间站 w）。
任何一条新航道被修建后，原本需要走 2 步的最短路径变为 1 步，使得通过该路径的有序对距离之和减少 1。问题转化为：在原始树的总距离和上，尽量多地减去新航道能够“节省”的距离。
