25976번 - k개 트리 노드에서 사과와 배를 최대로 수확하기

문제

n개의 노드와 n - 1개의 간선으로 구성된 트리 T가 있다. 노드 번호는 0부터 n - 1까지이고 0번 노드가 루트이다. 간선에는 가중치가 없다. 트리 T에 있는 각 노드는 사과가 1개 있는 노드, 배가 1개 있는 노드, 사과와 배가 모두 없는 노드로 구분된다. 루트 노드에서 시작하여 이웃한 노드를 방문하면서 사과와 배를 수확하려고 한다. 최대 k개의 노드를 방문하면서 사과와 배를 수확할 경우, 사과의 개수 × 배의 개수가 최대가 되는 사과의 개수와 배의 개수를 출력하자. 사과의 개수 × 배의 개수가 최대가 되는 경우가 여러 가지일 경우, 사과의 개수가 더 많은 경우를 출력하자. 사과의 개수 × 배의 개수가 최대이면서 사과의 개수가 같은 경우가 여러 가지일 경우 배의 개수가 더 많은 경우를 출력하자. 여러 번 방문한 노드도 한 번 방문한 것으로 생각한다. 루트 노드도 방문한 노드로 생각한다. 사과 또는 배가 있는 노드를 여러 번 방문해도 최초 한 번만 1개의 사과 또는 배를 수확할 수 있다.

입력

첫 번째 줄에 노드의 수 n과 정수 k가 공백을 사이에 두고 순서대로 주어진다.

두 번째 줄부터 n - 1개 줄에 걸쳐 간선의 정보가 주어진다. 한 줄에 하나의 간선 정보가 주어진다. 하나의 간선 정보는 부모 노드 번호 p와 자식 노드 번호 c가 공백을 사이에 두고 순서대로 주어진다.

다음 줄에는 0번 노드부터 n - 1번 노드까지 노드의 정보를 나타내는 n개의 정수가 공백을 사이에 두고 순서대로 주어진다. 즉, i번째 수는 i - 1번 노드의 정보를 나타낸다. 노드 정보가 0이면 사과와 배가 없는 경우, 1이면 사과만 1개 있는 경우, 2이면 배만 1개 있는 경우를 나타낸다.

출력

첫 번째 줄에 문제 조건에 맞는 사과의 개수와 배의 개수를 공백을 사이에 두고 순서대로 출력한다.

제한

• 1 ≤ k ≤ n ≤ 17
• 0 ≤ p, c ≤ n - 1, p ≠ c
• 간선들로 만들어진 그래프는 트리이다.
• 노드의 정보는 0 또는 1 또는 2이다.

힌트