내 풀이
from heapq import heappush, heappop
import sys
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 9)
input = sys.stdin.readline
n = int(input())
weights = [0] + list(map(int, input().split()))
tree = [[] for i in range(n + 1)]
dp = [[0] * 2 for i in range(n + 1)]
visit = [False for i in range(n + 1)]
path = [[[], []] for i in range(n + 1)]
def dfs(cur):
visit[cur] = True
dp[cur][0] = weights[cur]
path[cur][0].append(cur)
for child in tree[cur]:
if not visit[child]:
dfs(child)
dp[cur][0] += dp[child][1]
for j in path[child][1]:
path[cur][0].append(j)
if max(dp[child][1], dp[child][0]) == dp[child][1]:
dp[cur][1] += dp[child][1]
for k in path[child][1]:
path[cur][1].append(k)
else:
dp[cur][1] += dp[child][0]
for k in path[child][0]:
path[cur][1].append(k)
for i in range(n - 1):
a, b = map(int, input().split())
tree[a].append(b)
tree[b].append(a)
dfs(1)
if max(dp[1][0], dp[1][1]) == dp[1][0]:
print(dp[1][0])
a = path[1][0]
a.sort()
print(*a)
else:
print(dp[1][1])
a = path[1][1]
a.sort()
print(*a)dp[1][0]은 자기 자신을 포함했을 때 최대 값이고, dp[1][1]은 포함하지 않았을 때이다. dp[1][0]은 자기 자신을 포함하므로 자식을을 포함할 수 없으니 dp[1의 자식들][1]을 더해주면 된다. dp[1][1]은 자기 자신을 포함하지 않으므로 자식들을 포함할 수도 있고 안을 수도 있으니, dp[1의 자식들][0]과 dp[1의 자식들][1] 중 큰 값을 더해 나가면 된다.
출처: # https://pacific-ocean.tistory.com/332
