[Python]트리에서의 동적 계획법 백준 1949

문제

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

트리의 독립집합을 묻는 문제이다.

트리에서의 DP문제는 독립집합을 묻는 문제가 대부분인거 같다.

2213번 문제의 풀이를 그대로 가져와도 사용하여도 된다. 추적하는 부분만 빼면 풀이

법은 동일하다.

import sys
sys.setrecursionlimit(10**9)
 
n=int(sys.stdin.readline())
node_value=[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=[True for _ in range(n+1)]
def DFS(cur):
    check[cur]=False#방문체크
    DP[cur][0]=node_value[cur]#현재 노드 포함할때
    DP[cur][1]=0#현재 노드 포함하지 않을때
    for i in Tree[cur]:#연결된 노드 탐색
        if check[i]:#방문할수 있다면
            DFS(i)
            DP[cur][0]+=DP[i][1]#현재노드 방문했을때
            DP[cur][1]+=max(DP[i][0],DP[i][1])#현재노드 방문 안했을때
 
DFS(1)
print(max(DP[1][0],DP[1][1]))