Submission #66560060

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N = int(input())
x = list(map(int, input().split()))
tree = {}
weights = {}
for i in range(N-1):
    a, b, w = map(int, input().split())
    if a not in tree:
        tree[a] = set()
    if b not in tree:
        tree[b] = set()
    tree[a].add(b)
    tree[b].add(a)
    weights[(a, b)] = w
    weights[(b, a)] = w
costs = 0
while True:
    t = 0
    leafs = []
    for i in range(1,N+1):
        if len(tree[i]) == 1:
            l = list(tree[i])[0]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N = int(input())
x = list(map(int, input().split()))
tree = {}
weights = {}
for i in range(N-1):
    a, b, w = map(int, input().split())
    if a not in tree:
        tree[a] = set()
    if b not in tree:
        tree[b] = set()
    tree[a].add(b)
    tree[b].add(a)
    weights[(a, b)] = w
    weights[(b, a)] = w
costs = 0
while True:
    t = 0
    leafs = []
    for i in range(1,N+1):
        if len(tree[i]) == 1:
            l = list(tree[i])[0]
            costs += abs(x[i-1]) * weights[(i, l)]
            x[l-1] += x[i-1]
            x[i-1] = 0
            t += 1
            leafs.append((i, l))
    for leaf, leaf2 in leafs:
        if leaf2 in tree and leaf in tree[leaf2]:
            tree[leaf2].remove(leaf)
        tree[leaf] = set()
    if t == 0:
        break
print(costs)

Submission Info

Judge Result