Keeping the Tree Healthy

Yehwan likes playing with trees, so they built one out of tree branches. After some time, Yehwan noticed that some of the joints between branches are rotting. Yehwan wants to take a rose pruner and cut the fewest possible branches so that every connected component becomes healthy.

Call the points where branches meet nodes, and consider the graph $G$ formed by connecting nodes with edges (branches). Graph $G$ is a tree. A rotting node is called an unhealthy node. Yehwan considers a connected component healthy if it contains at most $K$ unhealthy nodes.

The figure above shows one way to split the tree into healthy parts when $K=2$. (Red nodes are unhealthy nodes.)

Given the total number of nodes $N$ and the maximum number of unhealthy nodes $K$ in a connected component, print the minimum number of edges to remove so that every remaining connected component is healthy.

The first line contains two integers $N$ and $K$, separated by a space.

The second line contains $N$ integers $H_1, H_2, \cdots, H_N$, separated by spaces. For each $1\leq i\leq N$, $H_i=1$ if node $i$ is an unhealthy node, and $H_i=0$ otherwise.

The next $N-1$ lines each contain two integers $U$ and $V$, separated by a space. This means an edge exists between node $U$ and node $V$.

Print the minimum number of edges to remove so that every remaining connected component is healthy.

• $1\leq N\leq 10^5$, $1\leq K\leq N$
• For each $1\leq i\leq N$, $H_i\in\{0, 1\}$
• $1\leq U\leq N$, $1\leq V\leq N$, $U\neq V$
• All given numbers are integers.
• The given graph is a tree.