白駿-優秀村(1949)

Tree + Dynamic Programming

質問する

1.'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

入力

しゅつりょく

import sys
sys.setrecursionlimit(10**9)
 
n = int(sys.stdin.readline())
nodeValue=[0] + list(map(int,sys.stdin.readline().split()))
Tree = [[] for _ in range(n + 1)]
DP = [[0,0] for _ in range(n + 1)]
 
for _ in range(n-1):
    a,b=map(int,sys.stdin.readline().split())
    Tree[a].append(b)
    Tree[b].append(a)
 
check=[False for _ in range(n+1)]

def DFS(current):
    check[current] = True
    DP[current][0] = nodeValue[current]
    DP[current][1] = 0
    for i in Tree[current]:
        if not check[i]:
            DFS(i)
            DP[current][0] += DP[i][1]
            DP[current][1] += max(DP[i][0],DP[i][1])
 
DFS(1)
print(max(DP[1][0], DP[1][1]))