Codeforces Round 202 (Div. 1) |
---|
Закончено |
Долгое время назад жили-были люди в стране Dudeland. Эта страна состояла из n городов, соединенных n - 1 двунаправленными дорогами. Города пронумерованы от 1 до n, и известно, что из любого города можно попасть в любой другой, двигаясь по дорогам страны. В Dudeland есть m монастырей, расположенных в m различных городах. В каждом монастыре живет пилигрим.
В начале года, каждый пилигрим записывает, какой монастырь находится дальше всего от того монастыря, в котором он живет. Если существует более одного такого монастыря, то он записывает все подходящие монастыри. В день Большого Лебовски каждый пилигрим выбирает наугад город из своего списка и начинает туда идти.
Уолтер ненавидит пилигримов и поэтому хочет прервать путь как можно большего числа пилигримов. Он планирует уничтожить ровно один город, в котором нет монастыря. Пилигрим огорчается, если все монастыри из его списка становятся недостижимыми из его монастыря.
Найдите максимальное количество пилигримов, которых Уолтер может огорчить. Также найдите количество способов, которым Уолтер может этого достигнуть — количество городов, которые он может удалить.
Первая строка содержит два целых числа n (3 ≤ n ≤ 105) и m (2 ≤ m < n). В следующей строке записано m различных целых чисел, обозначающих номера городов с монастырями.
Каждая из следующих n - 1 строк содержит три целых числа ai, bi, ci, обозначающих, что между городами ai и bi существует дорога длины ci (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 1000, ai ≠ bi).
Выведите два целых числа: максимальное количество пилигримов, которых Уолтер может огорчить, и количество способов, которыми он может осуществить свой план.
8 5
7 2 5 4 8
1 2 1
2 3 2
1 4 1
4 5 2
1 6 1
6 7 8
6 8 10
5 1
Название |
---|