728x90
https://www.acmicpc.net/problem/1949
1949번: 우수 마을
N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며,
www.acmicpc.net
역시 이전 글의 풀이와 동일하게 풀 수 있다.
루트 노드를 하나 잡은 후에, 밑에서부터 순회하면서 검사하면 된다.
자세한 설명은 이전 글을 참조하면 될 것 같다.
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
n = int(input())
population = [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)
visited= [False] * (n+1)
dp = [ [0,0] for _ in range(n+1) ]
def dfs(node):
visited[node] = 1
dp[node][1] = population[node]
for i in tree[node]:
if not visited[i]:
dfs(i)
dp[node][1] += dp[i][0]
dp[node][0] += max(dp[i][0],dp[i][1])
dfs(1)
print(max(dp[1][0],dp[1][1]))
728x90
'Python > 백준' 카테고리의 다른 글
11758_CCW (0) | 2022.05.22 |
---|---|
2166_다각형의 면적 (0) | 2022.05.21 |
2533_사회망서비스 (메모리초과,재귀오류?) (0) | 2022.05.18 |
2213_트리의 독립집합 (0) | 2022.05.18 |
15681_트리와쿼리 (0) | 2022.05.17 |