Agenci
시간 제한3초메모리 제한1024 MB
트리와 k명의 시작 위치가 주어지고, 하루에 한 명의 요원만 한 간선을 이동하며 각 도시는 한 요원만 방문할 수 있을 때, 모든 도시를 방문하는 최소 일수를 구한다.
문제
W Bajtocji działa k agentów. Muszą oni odwiedzić wszystkie n miast kraju, ale żeby nie wzbudzać podejrzeń kontrwywiadu:
- każdego dnia dokładnie jeden agent może przemieścić się z miasta, w którym się znajduje, do miasta z nim sąsiadującego;
- każde miasto może być odwiedzone tylko przez jednego agenta (ale być może wielokrotnie).
Sieć drogowa Bajtocji jest bardzo oszczędna i składa się z n−1 dróg. Z każdego miasta można dojść do każdego innego, być może przechodząc przez inne miasta.
Napisz program, który obliczy minimalną liczbę dni, w których agenci odwiedzą wszystkie miasta kraju. Zakładamy, że miasta, z których startują agenci, są już odwiedzone.
입력
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i k (2 ≤ n ≤ 500 000, 1 ≤ k ≤ n) oznaczające liczbę miast w Bajtocji i liczbę agentów. Miasta numerujemy liczbami od 1 do n.
W drugim wierszu wejścia znajduje się rosnący ciąg k liczb całkowitych z przedziału [1, n] oznaczający numery miast, które są początkowymi pozycjami agentów.
W kolejnych n − 1 wierszach znajduje się opis sieci drogowej Bajtocji. Każdy wiersz zawiera parę liczb całkowitych a, b (1 ≤ a, b ≤ n, a ≠ b) oznaczających, że istnieje droga łącząca miasta o numerach a i b.
출력
Twój program powinien wypisać na wyjście jeden wiersz zawierający jedną liczbę całkowitą oznaczającą minimalną liczbę dni, po których agenci odwiedzą wszystkie miasta Bajtocji.
힌트
Wyjaśnienie przykładu: Pierwszy agent może odwiedzić miasta 2 → 1 → 2 → 3, co zajmie mu 3 dni, a drugi agent miasta 6 → 5 → 4, co zajmie mu 2 dni.
