6191 : 트리 동적 계획법 - 배낭 문제
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
노드 u를 선택하려면 그 부모 노드가 선택되어야 한다는 종속 관계가 있습니다. 주어진 자원 한도 M 이내로 노드를 선택하여 얻을 수 있는 가치(이득)의 최댓값을 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 500)과 자원 한도 M (1 ≤ M ≤ 500)이 주어집니다.
둘째 줄부터 N개의 줄에 각 노드의 자원 소모량과 가치가 주어집니다.
그 다음 N-1개의 줄에 부모-자식 간선 정보 u, v가 주어집니다.
둘째 줄부터 N개의 줄에 각 노드의 자원 소모량과 가치가 주어집니다.
그 다음 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