Baekjoon-1949-우수 마을

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

N = int(input())
human = [0] + list(map(int, input().split()))
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    A,B = map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)

# DFS + DP로 접근
dp = [[0,0] for _ in range(N+1)]
# dp[i][0]: i마을이 우수마을이 아닐 때 해당 subtree의 우수마을 주민 수
# dp[i][1]: i마을이 우수마을일 때 해당 subtree의 우수마을 주민 수
visited = [0] * (N+1)
def dfs(u):
    visited[u] = 1
    for v in graph[u]:
        if visited[v] == 0:
            dfs(v)
            dp[u][0] += max(dp[v])
            dp[u][1] += dp[v][0]
    dp[u][1] += human[u]

dfs(1)
print(max(dp[1]))