6156 : 트리 DP — 독립 집합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
트리의 각 노드에 양의 가중치가 주어져 있습니다. 인접한 두 노드를 동시에 선택하지 않으면서 선택된 노드들의 가중치 합이 최대가 되도록 하는 최대 독립 집합의 가중치 합을 구하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄에 1번 노드부터 N번 노드까지의 가중치 N개가 공백으로 구분되어 주어집니다.
셋째 줄부터 N-1개의 줄에 간선 정보 u, v가 주어집니다.
둘째 줄에 1번 노드부터 N번 노드까지의 가중치 N개가 공백으로 구분되어 주어집니다.
셋째 줄부터 N-1개의 줄에 간선 정보 u, v가 주어집니다.
출력 설명
최대 독립 집합의 가중치 합의 최댓값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
10 20 30 40 50
1 2
1 3
2 4
2 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
120