P5865 [SEERC 2018] Tree

You are given a tree with $n$ vertices, numbered from $1$ to $n$. Each vertex is colored either black or white. Select exactly $m$ black vertices so that the maximum distance among all pairs of selected black vertices is minimized. Output this minimal possible maximum distance.

The first line contains two integers $n$ and $m \ (1 \leq m \leq n \leq 100)$, representing the number of vertices in the tree and the number of black vertices to be selected. The second line contains $n$ integers $p_1, p_2, \dots, p_n \ (0 \leq p_i \leq 1)$. If $p_i = 1$, then vertex $i$ is black; otherwise it is white. The testdata guarantees that there are at least $m$ black vertices. The next $n - 1$ lines each contain two integers $v_i$ and $u_i \ (1 \leq v_i, u_i \leq n)$, indicating that there is an edge between vertices $v_i$ and $u_i$ in the tree. The testdata guarantees that these edges form a tree.

Output one integer, which is the answer.

In the first sample, the only possible choice is to select vertices $1$, $2$, and $4$, and the maximum distance is $2$. In the second sample, one feasible choice is to select vertices $1$, $3$, $8$, and $9$. The maximum distance is the distance between vertices $3$ and $9$. Translated by ChatGPT 5