3
树可以通过去除其中的一条边而被分成两棵不同的树。给定一个带有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之间的边。
你能详细说明你卡在哪里吗?你有没有开始使用的任何代码? – Mikeb 2013-04-11 17:19:14