Pythonのサブツリーのノード値の合計から最小値を見つけるプログラム

すべてのノードに1からnまでの番号が付けられたツリーがあるとします。各ノードには整数値が含まれています。ここで、ツリーからエッジを削除する場合、2つのサブツリーのノード値の合計の差を最小限に抑える必要があります。そのようなサブツリー間の最小の違いを見つけて返す必要があります。ツリーはエッジのコレクションとして提供され、ノードの値も提供されます。

したがって、入力が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：=0で初期化されたサイズnの新しいリスト
• not_visited：=サイズiの新しいマップ。ここで、iはadj_list内の空でないリストの数です
• not_visitedが空ではない場合は、
  • not_visitedの各iについて、
    • value_list [i]：=value_list [i] + values [i]
    • （adj_list [i]）の長さがゼロ以外の場合、
      • adj_list [adj_list [i、0]]からiを削除します
      • 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：=decision_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