{"code":"div2dolpmttn","name":"Cây đỏ đen","description":"Bạn được cho một cây có $n$ đỉnh, mỗi đỉnh đều có màu trắng hoặc màu đen. Hãy chọn chính xác $m$ đỉnh màu đen sao cho khoảng cách lớn nhất giữa $2$ đỉnh màu đen là nhỏ nhất. \r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên chứa hai số nguyên dương $n$ và $m(2 \\leq m \\leq n \\leq 100)$ - số đỉnh của đồ thị và số đỉnh màu đen bạn phải chọn.\r\n- Dòng thứ hai chứa $n$ số nguyên $p_1, p_2, ..., p_n(0 \\leq p_i \\leq 1)$. Nếu $p_i=1$ thì nút thứ $i$ có màu đen, $p_i=0$ thì nút có màu trắng.\r\n- $n-1$ dòng tiếp theo chứa hai số nguyên dương $u_i$ và $v_i(1 \\leq u_i, v_i \\leq n)$, giữa hai đỉnh $u_i$ và $v_i$ có cạnh nối.\r\n- Input luôn đảm bảo có cách chọn $m$ đỉnh màu đen từ đồ thị.\r\n\r\n

Output

\r\n\r\n- Giá trị nhỏ nhất khoảng cách lớn nhất trong các cách chọn $m$ đỉnh màu đen.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($40\\%$ số điểm): $m = 2$.\r\n- Subtask $2$ ($60\\%$ số điểm): $m > 2$.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 6 3 \r\n 1 1 0 1 1 1\r\n 1 2\r\n 1 3\r\n 1 4\r\n 3 5\r\n 3 6\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 2\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n ![](https://i.imgur.com/5xDXNbr.png)\r\n\r\n Chọn $3$ đỉnh $(1, 2, 4)$. Khoảng cách lớn nhất chính là khoảng cách từ đỉnh $2$ đến đỉnh $4$.","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":1048000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}