Python中从子树的节点值之和中找出最小值的程序

假设我们有一棵树，它的所有节点都编号为 1 到 n。每个节点都包含一个整数值。现在，如果我们从树中删除一条边，则两个子树的节点值之和的差异必须最小。我们必须找出并返回这些子树之间的最小差异。树作为边的集合提供给我们，并且还提供了节点的值。

所以，如果输入像 n = 6，edge_list = [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], values = [15, 25, 15, 55, 15, 65]，那么输出将为 0。

如果边 (1,2) 被移除，权重之和变为 80、110。差值为 30。

如果边 (1,3) 被移除，则权重之和变为 95、95。差为 0。

如果边 (2,4) 被移除，权重之和变为 55、135。差值为 80。

如果边 (3,5) 被移除，权重之和变为 15, 175。差值为 160。

如果边 (3,6) 被删除，权重之和变为 65, 125。差为 60。

所以最小权重为0。

示例

让我们看看以下实现以更好地理解 -

def solve(n, edge_list, values):
   adj_list = [[] for i in range(n)]

   for edge in edge_list:
      u = edge[0]
      v = edge[1]
      adj_list[u-1].append(v-1)
      adj_list[v-1].append(u-1)

   value_list = [0] * n
   not_visited = {i for i in range(n) if len(adj_list[i]) == 1}
   while(len(not_visited)):
      for i in not_visited:
         value_list[i] += values[i]
         if(len(adj_list[i])):
            adj_list[adj_list[i][0]].remove(i)
            value_list[adj_list[i][0]] += value_list[i]
      not_visited = {adj_list[i][0] for i in not_visited if
         len(adj_list[i]) and len(adj_list[adj_list[i][0]]) == 1}
   return_val = abs(sum(values) - 2 * value_list[0])

   for i in range(1, n):
      decision_val = abs(sum(values) - 2 * value_list[i])
      if decision_val < return_val:
         return_val = decision_val
   return return_val

print(solve(6, [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], [10, 20, 10, 50, 10, 60]))

输入

6, [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], [10, 20, 10, 50, 10, 60]

0