Untitled

unknown
plain_text
2 years ago
1.6 kB
2
Indexable
Never
```from collections import deque
import copy

def BFS(graph, is_in_deque, source, layer):
queue = deque()
queue.append(1)
is_in_deque[1] = True
layer[1] = 0
while len(queue):
from_ = queue.popleft()
for to in graph[from_]:
if not is_in_deque[to]:
source[to].append(from_)
is_in_deque[to] = True
queue.append(to)
layer[to] = layer[from_]+1
ans_lst[from_] += num_lst[from_]
ans_lst[1] += sum(num_lst)
print(source)  # 每個node的上面一個node的位置
print(layer)  # 每個node所在層數
print(ans_lst)
result_lst = copy.deepcopy(ans_lst)
for i in range(1, len(layer)-1):  # 下往上加
if result_lst[i] == 0:
max_place = layer.index(max(layer))
ans_lst[max_place] += num_lst[max_place]
layer[max_place] = -1
ans_lst[source[max_place][0]] += ans_lst[max_place]
# ans_lst[1] += num_lst[1]

n = int(input())
ans_lst = [0 for _ in range(n+1)]
num_lst = list(map(int, input().split()))
num_lst.insert(0, 0)
tree = [[] for _ in range(n+1)]
for i in range(n-1):
u, v = map(int, input().split())
tree[u].append(v)
tree[v].append(u)
source = [[] for _ in range(n+1)]
is_in_deque = [False for _ in range(n + 1)]
layer = [-1 for _ in range(n + 1)]
BFS(tree, is_in_deque, source, layer)

for i in range(1, len(ans_lst)):
print(ans_lst[i], end=' ')```