树中的边缘切割

Question

树可以通过去除其中的一条边而被分成两棵不同的树。给定一个带有N节点的树，该节点由[0, N-1]范围内的整数唯一标识，我需要编写一个函数来查找需要从树中移除的边，从而使得结果中所有节点ID的总和之差树木被最小化。

该函数应打印它找到的与标准输出（stdout）的最小差异。

该函数将接收下列参数：

parent这是整数的数组具有以下含义：parent[i] =节点i（更具体地其ID）

parent[i] = -1如果i具有的父没有父（i是该树的根）

数据约束

树中的节点的最大数目为50000个

效率约束

功能预计在小于2秒

打印结果实施例

Input parent: [1, 4, 4, 2, -1, 2, 2] 

aka :   4 
      /\ 
      1 2 
      // | \ 
      0 3 5 6 

Output: 9 

说明：我们删除了节点2和节点6之间的边。

Answer 1

1. 对于每个节点，计算其子节点的总和，然后将此值添加到自身，并将其存储在节点中。我们称这个值为S_n，其中n是一个节点。 （可通过递归&后序遍历很容易做到）

2. 找哪家S_n有向S_root/2差最小的节点n。 n和它的父代之间的边是我们想要的边。 （这在最坏的情况下需要线性时间。）