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

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

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

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

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

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

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