k개 트리 노드에서 사과를 최대로 수확하기
면접 대비시간 제한3초메모리 제한512 MB
각 노드에 사과가 0개 또는 1개 있는 루트 트리에서 루트부터 시작해 최대 k개 노드를 방문할 때 수확할 수 있는 사과 개수의 최댓값을 구한다.
문제
n개의 노드와 n - 1개의 간선으로 구성된 트리 T가 있다. 노드 번호는 0부터 n - 1까지이고 0번 노드가 루트이다. 간선에는 가중치가 없다. 트리 T의 각 노드에는 사과가 0개 또는 1개 놓여있다. 루트 노드에서 시작하여 이웃한 노드를 방문하면서 사과를 수확하려고 한다. 최대 k개의 노드를 방문하면서 수확할 수 있는 사과 개수의 최댓값을 출력하자. 여러 번 방문한 노드도 한 번 방문한 것으로 생각한다. 루트 노드도 방문한 노드로 생각한다. 사과가 있는 노드를 여러 번 방문해도 최초 한 번만 1개의 사과를 수확할 수 있다.
입력
첫 번째 줄에 노드의 수 n과 정수 k가 공백을 사이에 두고 순서대로 주어진다.
두 번째 줄부터 n - 1개 줄에 걸쳐 간선의 정보가 주어진다. 한 줄에 하나의 간선 정보가 주어진다. 하나의 간선 정보는 부모 노드 번호 p와 자식 노드 번호 c가 공백을 사이에 두고 순서대로 주어진다.
다음 줄에는 0번 노드부터 n - 1번 노드까지 노드의 사과 정보를 나타내는 n개의 정수가 공백을 사이에 두고 순서대로 주어진다. i번째 수는 i - 1번 노드에 있는 사과의 수를 나타낸다. 사과의 수는 0 또는 1이다.
출력
첫 번째 줄에 수확할 수 있는 사과 개수의 최댓값을 출력한다.
제한
- 1 ≤ k ≤ n ≤ 17
- 0 ≤ p, c ≤ n - 1, p ≠ c
- 간선들로 만들어진 그래프는 트리이다.
- 노드에 있는 사과의 수는 0 또는 1이다.