트리
시간 제한1초메모리 제한512 MB
트리에서 검은색 정점 m개를 골라 선택된 정점 사이의 최대 거리를 최소로 만들려고 합니다.
문제
1부터 n까지의 번호가 각각 다르게 붙은 n개의 정점으로 이루어진 트리가 주어진다. 각 정점은 검은색 또는 흰색이다. 검은색 정점 m개를 정확히 선택해서, 선택한 정점 사이의 가장 긴 경로의 길이가 최소가 되도록 하라.
입력
첫째 줄에 두 정수 n과 m이 주어진다 (1 ≤ m ≤ n ≤ 100). n은 정점의 수, m은 선택해야 하는 검은색 정점의 수다.
넷째 줄에 n개의 정수 p1, p2, . . . , pn이 주어진다 (0 ≤ pi ≤ 1). pi = 1이면 i번 정점은 검은색이고, 그렇지 않으면 흰색이다. 검은색 정점의 수는 m 이상임이 보장된다. 다음 n − 1개의 줄에는 두 정수 vi와 ui가 주어진다 (1 ≤ vi, ui ≤ n). 이는 vi와 ui 사이에 간선이 있음을 뜻한다.
입력으로 주어지는 그래프는 트리임이 보장된다.
출력
정수 하나를 출력한다. 문제의 답이다.
힌트
첫 번째 예시에서는 1, 2, 4를 선택하는 방법밖에 없다. 최대 거리는 2가 된다.
두 번째 예시에서는 1, 3, 8, 9를 선택할 수 있다. 최대 거리는 3과 9 사이의 거리다.