32521번 - 팩트는 트리가 건강해지고 있다는 거임

문제

트리를 가지고 노는 것을 좋아하는 예환이는 나뭇가지로 하나의 트리를 만들었다. 하지만 시간이 지나자 나뭇가지들의 접합부 중 몇몇이 썩고 있다는 것을 발견했다. 예환이는 곧바로 장미칼을 가져와서 최소 개수의 나뭇가지들을 잘라내어 모든 연결 요소들이 건강해지게 만들고 싶다.

나뭇가지들이 만나는 접합부를 노드라고 할 때, 노드들을 간선(나뭇가지)으로 연결한 그래프 $G$를 생각하자. 그래프 $G$는 트리(수형도)이다. 썩고 있는 노드를 안 건강 노드라고 하자. 예환이는 하나의 연결 요소 속 안 건강 노드의 개수가 $K$를 넘지 않으면 그 연결 요소를 건강하다고 판단한다.

위의 그림은 $K=2$일 때 트리를 건강하게 나눈 예시 중 하나이다. (빨간 노드가 안 건강 노드를 의미한다.)

총 노드의 수 $N,ドル 한 연결 요소 속 안 건강 노드의 최대 개수 $K$가 주어졌을 때, 최소 몇 개의 간선을 없앴을 때 남은 모든 연결 요소들이 건강해지는지 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 두 정수 $N,ドル $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $H_1, H_2, \cdots, H_N$가 공백으로 구분되어 주어진다. 각 1ドル\leq i\leq N$에 대하여, $i$번째 노드가 안 건강 노드이면 $H_i=1$이고 그렇지 않으면 $H_i=0$이다.

이후 $N - 1$개의 줄에 걸쳐 각 줄마다 두 정수 $U,ドル $V$가 공백으로 구분되어 주어진다. 이는 $U$번째 노드와 $V$번째 노드 사이를 잇는 간선이 존재한다는 의미이다.

출력

최소 몇 개의 간선을 없앴을 때 남은 모든 연결 요소들이 건강해지는지 출력한다.

제한

• 1ドル\leq N\leq 10^5,ドル 1ドル\leq K\leq N$
• 각 1ドル\leq i\leq N$에 대하여, $ H_i\in\{0, 1\}$
• 1ドル\leq U\leq N,ドル 1ドル\leq V\leq N,ドル $U\neq V$
• 주어지는 모든 수는 정수이다.
• 주어지는 그래프는 트리이다.

힌트