Sadonkorjuu

n = int(input())
k = input().split(" ")
k = list(map(int, k))
edges = []
for i in range(n - 1):
    a = input().split(" ")
    a = list(map(int, a))
    edges.append([a[0], a[1], a[2]])
graph = {}
for edge in edges:
    a, b, c = edge[0], edge[1], edge[2]
    if a not in graph.keys():
        graph[a] = []
    if b not in graph.keys():
        graph[b] = []
    graph[a].append([b, c])
    graph[b].append([a, c])

if len(graph.keys()) == 0: graph[1] = [[1, 0]]

def leveyshaku():
    q = [1]
    visited = [1]
    heights = {1: 1}
    e = {1: 0}
    while q:
        s = q.pop(0)
        for u in graph[s]:
            if u[0] in visited: continue
            visited.append(u[0])
            e[u[0]] = e[s] + u[1]
            heights[u[0]] = heights[s] + 1
            q.append(u[0])
    return e, heights

z = []
euler = {}
depth = []
def eulerTree(u, index):
    z.append(u)
    euler[index] = u
    depth.append(heights[u])
    index += 1
    for nbr in graph[u]:
        if nbr[0] not in z:
            index = eulerTree(nbr[0], index)
            euler[index] = u
            depth.append(heights[u])
            index += 1
    return index

def lca(node1, node2):
    minDist = 9999999999999
    for i in range(len(euler)):
        for j in range(i + 1, len(euler)):
            if (node1 == euler[i] and node2 == euler[j] or node2 == euler[i] and node1 == euler[j]) and minDist > abs(i-j):
                m = (min(i, j), max(i, j) + 1)
                minDist = abs(i-j)
    return min(depth[m[0]:m[1]])

def dist(pelto, satama):
    return values[pelto + 1] + values[satama + 1] - 2 * values[lca(pelto + 1, satama + 1)]

def findSatamas(pelto):
    satamas = []
    visited = [pelto]
    queue = [pelto]

    while queue:
        s = queue.pop(0)
        for neighbour in graph[s]:
            if neighbour[0] not in visited:
                if k[neighbour[0] - 1] == 0:
                    satamas.append(neighbour[0])
                else:
                    queue.append(neighbour[0])
                visited.append(neighbour[0])
    return satamas

values, heights = leveyshaku()
eulerTree(1, 1)
euler = list(euler.values())

ans = 0
while 1 in k:
    pelto = k.index(1)
    satamas = findSatamas(pelto + 1)
    costs = []
    for satama in satamas:
        costs.append(dist(pelto, satama - 1))
    ans += min(costs)
    k[pelto] = 2

print(ans)

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 1, 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 81, in <module>
    e...

Test 16

Group: 1, 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 81, in <module>
    e...

Test 17

Group: 1, 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 81, in <module>
    e...

Test 18

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED