백준 1949 - 우수 마을 (파이썬)

dp에서 0이면 자기자신이 우수 마을인 경우라 생각하고 풀면됩니다.

import sys

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
costs = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)

for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

dp = [[0, 0] for _ in range(n + 1)]

def dfs(num):
    visited[num] = True
    dp[num][0] = costs[num]
    
    for i in graph[num]:
        if not visited[i]:
            dfs(i)
            dp[num][0] += dp[i][1]
            dp[num][1] += max(dp[i][0], dp[i][1])

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