Мінімальна відстань
Limits: 2 sec., 256 MiB
Задано зв’язний граф з \(n\) вершин і \(n-1\) ребер, а також деяку множину \(P\) вершин цього графа.
Знайдіть таку вершину, що сумарна відстань від неї до всіх вершин з множини \(P\) мінімальна, і виведіть цю відстань.
Input
У першому рядку задано два цілі числа \(n\) і \(k\), де \(n\) — кількість вершин в графі, а \(k\) — кількість вершин в множині \(P\).
В наступних \(n-1\) рядках задано по два цілі числа \(a_i\) і \(b_i\) (\(1 \le a_i, b_i \le n\)). Кожна така пара утворює ребро в графі.
В наступному рядку задано \(k\) різних цілих чисел \(p_i\) (\(1 \le p_i \le n\)) — вершини що утворюють множину \(P\).
Output
У єдиному рядку виведіть одне ціле число — відповідь на задачу.
Constraints
33% тестів: \(1 \le n, k \le 100\)
33% тестів: \(1 \le n \le 10^5, 1 \le k \le 100\)
34% тестів: \(1 \le n, k \le 10^5\).
Samples
Input (stdin) | Output (stdout) |
---|---|
8 4 1 2 1 3 1 4 4 6 4 5 5 7 5 8 2 5 6 7 | 6 |
Notes
У прикладі до множини \(P\) належать чотири вершини: 2, 5, 6 і 7. Сумарна відстань до них від вершини 4 дорівнює 6 (відстань від 4 до 2 рівна 2, відстань від 4 до 6 рівна 1, відстань від 4 до 5 рівна 1, відстань від 4 до 7 рівна 2). Також мінімальна відстань досягається в вершині 5. Для решти вершин сумарна відстань є більшою.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|