Untitled

mail@pastecode.io avatar
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()
        add = 0
        for to in graph[from_]:
            if not is_in_deque[to]:
                source[to].append(from_)
                is_in_deque[to] = True
                queue.append(to)
                add += 1
                layer[to] = layer[from_]+1
        if add == 0:
            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=' ')