3

一棵树可以通过删除其中一条边分成两棵不同的树。给定一棵树，其N节点由范围内的整数唯一标识[0, N-1]，我需要编写一个函数来查找需要从树中删除的边，这样生成的树中所有节点 ID 的总和之间的差是最小化。

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

该函数将接收以下参数：

parent这是一个整数数组，具有以下含义：parent[i]= 节点的父节点i（更具体地说，它的 ID）

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

数据约束

树中的最大节点数为 50,000

效率限制

该函数预计在 2 秒内打印结果

例子

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

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

 Output: 9

解释：我们删除节点 2 和 6 之间的边。

4

1 回答 1

2

  1. 对于每个节点，计算其子节点的总和，然后将此值添加到自身，并将其存储在节点中。S_n让我们将此值n称为节点。（可以通过递归和后序遍历轻松完成）

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

于 2013-04-11T21:45:40.390 回答