Python에서 하위 트리의 노드 값의 합에서 최소값을 찾는 프로그램

<시간/>

모든 노드가 1부터 n까지 번호가 매겨진 트리가 있다고 가정합니다. 각 노드는 정수 값을 포함합니다. 이제 트리에서 가장자리를 제거하면 두 하위 트리의 노드 값 합계의 차이가 최소화되어야 합니다. 이러한 하위 트리 간의 최소 차이를 찾아 반환해야 합니다. tree는 edge의 집합체로 우리에게 주어지며, node의 값도 함께 제공된다.

따라서 입력이 n =6, edge_list =[[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], values =[15, 25, 15, 55, 15, 65], 출력은 0이 됩니다.

edge(1,2)를 제거하면 weight의 합은 80, 110이 되고 차이는 30이 된다.

edge(1,3)을 제거하면 weight의 합은 95,95가 되고 차이는 0이 된다.

edge(2,4)를 빼면 weight의 합은 55,135가 되고 차이는 80이 된다.

edge(3,5)를 빼면 weight의 합은 15,175가 되고 차이는 160이 된다.

edge(3,6)를 빼면 weight의 합은 65,125가 되고 차이는 60이 된다.

따라서 최소 가중치는 0입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

adj_list :=빈 목록을 포함하는 크기 n의 새 목록
edge_list의 각 가장자리에 대해 다음을 수행합니다.
- u :=가장자리[0]
- v :=가장자리[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가 비어 있지 않은 동안 do
- not_visited의 각 i에 대해 다음을 수행합니다.
  - value_list[i] :=value_list[i] + values[i]
  - (adj_list[i])의 길이가 0이 아니면
    - 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 :=|합계(값) - 2 * 값 목록[0]|
1~n 범위의 i에 대해
- decision_val :=|합(값) - 2 * 값_목록[i]|
- decision_val
- return_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]