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。

为了解决此问题，我们将执行以下步骤：

• adj_list父节点：一个新列表，大小为n，包含空列表
• 对于edge_list中的每个边，执行以下操作：
  • u = edge[0]
  • v = edge[1]
  • 将v-1插入adj_list [u-1]末尾
  • 将u-1插入adj_list [v-1]末尾
• value_list：一个初始化为0的大小为n的新列表
• not_visited：大小为i的新地图，其中i是adj_list中非空列表的数量
• while not_visited不为空，执行以下操作：
  • for循环中的i in not_visited，执行以下操作：
    • value_list [i] = value_list [i] + values [i]
    • 如果 (adj_list [i] ) 的长度非零，则删除i的邻接列表[adj_list [i，在0]中的 i ]
    • value_list [adj_list [i，在0]] = value_list [adj_list [i，在0]] + value_list [i]
  • for i in not_visited中的每个i，执行以下操作：
    • 如果len(adj_list [i]）和 len(adj_list [adj_list [i，在0]]） 1，则
    • not_visited =包含adj_list [i，在0]的新列表
• return_val：|sum（values）-2*value_list [0] |的值
• 对于i在范围1到n的循环，执行以下操作：
  • decision_val：|sum（values）-2*value_list [i] |的值
  • 如果decision_val
  • return_val：=decision_val

  • return return_val

示例

看下面的实现以更好地理解此示例−

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