[백준][DFS+DP] 우수 마을

우수 마을

 

 

• 풀이
  • DFS+DP
  • sys.setrecursionlimit(10**6) 안하면 런타임 에러

• ‘우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.
  • ⇒ 선정되지 않은 마을 끼리도 붙어있을 수 있다 
• 루트 노드는 1개의 노드만 붙음
  • ⇒ 루트, 자식 노드 모두 선정되지 않아도 됨
• 값을 넣어주기 전에 탑다운으로 뒷부분 dfs가 먼저 돌아줘야한다
  • 루트 노드를 우수마을로 선택 X → 자식노드 선택 중에 최댓값
  • 루트 노드를 우수마을로 선택 O → 무조건 자식노드는 선택 X

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

n = int(input())
village = [0] + list(map(int, input().split()))
graph = defaultdict(list)

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

def dfs(start):
    visited[start]=True

    for next in graph[start]:
        if not visited[next]:
            dfs(next) #뒤에가 먼저 돌아줘야함
            dp[start][0] += max(dp[next][0], dp[next][1])
            dp[start][1] += dp[next][0]


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