2213_트리의 독립집합

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

2213번: 트리의 독립집합

 

 

문제에 나온 트리는 1번을 루트노드라고 생각한다면

 

위와 같은 구성을 가지게 된다.

 

그렇다면 어떻게 하면 가중치를 더해갈 수 있을지 생각해보자.

 

먼저 자식부터 검사를 하는 것이 좋을 것이다.

 

5->4->3->7->6->2->1 순서로 탐색을 한다.

 

어떤부분을 탐색할때 자식노드와 부모 노드가 있다고 생각하면, 부모노드가 독립집합 안에 속해있다면 자식노드는 속할 수 없고 부모노드가 속해있지 않다면 자식노드는 속해있거나 속해있지 않을 것이다.

 

즉

 

부모노드가 독립집합에 속해있음   ===>   자식노드들이 속해있지 않은 가중치들의 합

부모노드가 독립집합에 속해있지 않음 =>  자식노드들의 가중치들 중 큰 값들의 합

 

으로 표현할 수 있다.

 

연산중에 노드를 기록해 나갈 count배열을 하나 만들어 기록해 나가면서 기록하면 원하는 답을 출력해낼 수 있다.

 

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
w = [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)

dp = [ [0,0] for _ in range(n+1) ]
count = [ [[],[]] for _ in range(n+1)]
visited = [ False ] * (n+1)
def dfs(node):
    visited[node] = True
    dp[node][1] = w[node]
    count[node][1] += [node]
    for i in tree[node]:
        if not visited[i]:
            dfs(i)
            dp[node][1] += dp[i][0]
            count[node][1]+=(count[i][0])
            if dp[i][0] > dp[i][1]:
                dp[node][0] += dp[i][0]
                count[node][0] += count[i][0]
            else:
                dp[node][0] += dp[i][1]
                count[node][0] += count[i][1]
dfs(1)
if dp[1][1] > dp[1][0]:
    print(dp[1][1])
    count[1][1].sort()
    print(*count[1][1])
else:
    print(dp[1][0])
    count[1][0].sort()
    print(*count[1][0])