16328번 - Tree 다국어

문제

You are given a tree of n vertices, each with a unique number from 1 to n. A vertex has a color, black or white. Choose exactly m black vertices so that the length of the longest path between any of them is minimal.

입력

The first line contains two integers n and m (1 ≤ m ≤ n ≤ 100) — the number of vertices and the number of black vertices you have to choose.

The fourth line contains n integers p₁, p₂, . . . , p_n (0 ≤ p_i ≤ 1). If the p_i = 1, then the i-th vertex is black; otherwise, it is white. It is guaranteed that the number of black vertices is at least m. Each of the next n − 1 lines contains two integers v_i and u_i (1 ≤ v_i , u_i ≤ n) meaning that there is an edge between v_i and u_i.

It is guaranteed that the input graph is a tree.

출력

Print a single integer — the answer to the task.

제한

힌트

In the first example, the only option is to choose 1, 2, and 4. The maximum distance will be 2.

In the second example, you can choose 1, 3, 8, and 9. The maximum distance will be between 3 and 9.