6157 : 트리 DP — 경로 최대합

시간 2.000s · 메모리 256MB · 제출 0 · 정답 0

코드제출 문제 풀기

채점기록 통계 묻고답하기

트리의 각 노드에 가중치가 주어져 있습니다(가중치는 음수일 수 있음). 트리 상의 임의의 두 노드를 연결하는 단순 경로 중, 경로에 포함된 노드들의 가중치 합의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄에 각 노드의 가중치 N개가 공백으로 구분되어 주어집니다.
셋째 줄부터 N-1개의 줄에 간선 정보 u, v가 주어집니다.

트리 상의 단순 경로 가중치 합의 최댓값을 출력합니다.

5
10 -2 3 4 -5
1 2
1 3
2 4
2 5