Submission #1748707

---

Source Code Expand

import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def dfs(now, parent, h_list, graph):
    use = h_list[now] * 2
    ans = 0
    for c in graph[now]:
        if c == parent:
            continue
        cost = dfs(c, now, h_list, graph)
        if cost > 0:
            use = 2
            ans += cost
    return use + ans


def main():
    n, x = map(int, input().split())
    x -= 1
    h_list = list(map(int, input().split()))
    h_list[x] = 0
    graph = defaultdict(list)
    for _ in range(n - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    ans = dfs(x, -1, h_list, graph)
    print(max(0, ans - 2))


if __name__ == '__main__':
    main()

Submission Info

Judge Result