树中的中心节点（距离最小和）

Question

我的问题如下：

给定一棵树(V, E)，找到中心节点v使得sum{w in V}[dist(v,w)]最小，其中dist(v,w)为边数从 v 到 w 的最短路径。该算法应该在 O(n) 时间内运行（n 是树中的节点数）。

问题 here and here 也要求中心节点，但定义不同。

我没有严格执行这些步骤，但实际上我认为我的问题的解决方案应该与 this problem 的解决方案类似。

但是，我决定与社区分享我的问题，因为我花了一些时间才导航到 the link，但它并没有直接回答问题。

Answer 1

每条边 e={a,b} 具有以下属性：

a_count = 边的节点数（包括a）
b_count = b端节点数（包括b）
a_sum = a 到其子树节点的距离总和
b_sum = b 到其子树节点的距离之和

节点 e={a,b} 的

a_count 可以计算如下： * 获取 a 的所有边，不包括 e，求和 a_count * 总和加 1

节点 e={a,b} 的

a_sum 可以计算如下： * 获取 a 的所有边，不包括 e，求和 a_sum *添加a_count（它包括每个枚举边的+1和a的+1）

你可以在接受节点和方向参数的递归函数中自由计算，将得到的结果保存在全局数组中。

如果您运行在树的每条边上双向执行此函数，您将获得边的完整计算。所有计算的总时间是 O(n)，因为一旦你到达某个子树，递归性质将关闭这个方向的整个子树，下一次调用将从全局数组中获取结果，而你只对你的函数进行 2*n 次调用.

对于节点最终的度量是连接到节点的所有边的所有 B_count+B_sum 的总和。在节点和具有最小值的 select 节点上执行此评估的一项运行。

Answer 2

我想到了这个解决方案：

1) 选择任意一个节点作为根r，形成一棵树。对于这棵树中的每个子树，计算子树中的节点数（叶子是单节点树）。

以此树为例

          1
        / | \
       2  3  4 
      / \     \
     5   6     7
        / \
       8   9

结果会是

          9
        / | \
       5  1  2 
      / \     \
     1   3     1
        / \
       1   1

2) 计算所选根的距离总和。例如，如果您选择顶点 1 作为根，则距离之和为 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3 = 15

3) 以depth-first-search的方式遍历树。例如，从顶点 1 开始，我们遍历到顶点 4。我们观察到对于 7 个节点（1,2,3,5,6,8,9），我们进一步移动了 1（将 7=9-2 添加到得分），对于其他2（4,7），我们越来越接近1（减去2）。这给出的距离总和等于 15+(9-2)-2 = 20。

假设我们接下来从4遍历到7。现在我们得到的距离总和等于 20+(9-1)-1 = 27（离 8 个顶点越远，离 1 个顶点越近）。

再举一个例子，如果我们从1遍历到2，我们得到的距离之和等于15+(9-5)-5 = 14。顶点2实际上就是这个例子的解。

这就是我的算法。

树中的中心节点（距离最小和）

Center node in a tree (in a minimum sum of distances sense)

algorithm

graph-theory