1949_우수마을

https://www.acmicpc.net/problem/1949

1949번: 우수 마을

 

 

 

역시 이전 글의 풀이와 동일하게 풀 수 있다.

 

루트 노드를 하나 잡은 후에, 밑에서부터 순회하면서 검사하면 된다.

 

자세한 설명은 이전 글을 참조하면 될 것 같다.

 

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

n = int(input())
population = [0]+list(map(int,input().split()))

tree = [ [] for _ in range(n+1) ]
for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
visited= [False] * (n+1)
dp = [ [0,0] for _ in range(n+1) ]

def dfs(node):
    visited[node] = 1
    dp[node][1] = population[node]

    for i in tree[node]:
        if not visited[i]:
            dfs(i)
            dp[node][1] += dp[i][0]
            dp[node][0] += max(dp[i][0],dp[i][1])


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