6181 : 트리 DP 심화
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
트리의 각 노드에 무게와 가치가 주어집니다. 부모 노드를 선택해야만 자식 노드를 선택할 수 있는 종속성 배낭 조건 하에서, 선택된 노드들의 무게 합이 W 이하가 되도록 노드를 선택할 때 가치 합의 최댓값을 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 2,000)과 배낭의 한도 W (1 ≤ W ≤ 10,000)가 주어집니다.
둘째 줄부터 N개의 줄에 각 노드의 무게와 가치가 주어집니다. (1번 노드가 루트입니다.)
그 다음 N-1개의 줄에 부모-자식 간선 정보 u, v가 주어집니다.
둘째 줄부터 N개의 줄에 각 노드의 무게와 가치가 주어집니다. (1번 노드가 루트입니다.)
그 다음 N-1개의 줄에 부모-자식 간선 정보 u, v가 주어집니다.
출력 설명
선택한 노드들의 가치 합의 최댓값을 첫째 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 10
2 3
3 4
4 8
2 5
1 2
1 2
1 3
2 4
2 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
17