시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB86373247.059%

문제

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 ≤ kn ≤ 17
  • 0 ≤ p, cn - 1, pc
  • 간선들로 만들어진 그래프는 트리이다.
  • 노드의 정보는 0 또는 1 또는 2이다.

예제 입력 1

7 1
0 1
0 2
1 3
1 4
2 5
2 6
1 1 2 2 2 2 1

예제 출력 1

2

노드 0, 노드 2, 노드 5를 방문하여 배를 2개 수확하는 게 정답이다.

예제 입력 2

7 2
0 1
0 2
1 3
1 4
2 5
2 6
1 1 2 2 2 2 1

예제 출력 2

4

노드 0, 노드 1, 노드 2, 노드 3, 노드 4, 노드 5를 방문하여 배를 4개 수확하는 게 정답이다.

출처