HTML CSS JAVASCRIPT JQUERY AI PHP SQL EXCEL LINUX C# C++ C PYTHON JAVA 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ

用 Python 编写程序，从子树节点值的总和中找出最小值

pythonserver side programmingprogramming更新于 2026/1/30 12:28:17

假设，我们有一棵树，它的所有节点都编号为 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]
    • 在 adj_list[u-1] 末尾插入 v-1
    • 在 adj_list[v-1] 末尾插入 u-1
  • value_list := 一个大小为 n 的新列表，用 0 初始化
  • not_visited := 一个大小为 i 的新映射，其中 i 是 adj_list 中非空列表的数量
  • 当 not_visited 不为空时，执行
    • 对于 not_visited 中的每个 i，执行
      • value_list[i] := value_list[i] + values[i]
      • 如果 (adj_list[i]) 的长度非零，则
        • 从中删除 i adj_list[adj_list[i, 0]]
        • value_list[adj_list[i, 0]] := value_list[adj_list[i, 0]] + value_list[i]
    • 对于 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]|
  • 对于范围从 1 到 n 的 i，执行
    • decision_val := |sum(values) - 2 * value_list[i]|
    • 如果 decision_val < return_val，则
      • return_val := decision_val
  • 返回 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

相关文章

有用资源

打印 下一节:用 Python 编写程序，找出让市民进入市场所需的最低成本 ❯❮ 上一节:如何在 Python 中捕获 IOError 异常?