Задача №113791. Пандемия 2
Друзья Васи постоянно играют в настольную игру «Пандемия». Васе это немного надоело, поэтому он решил создать свою версию этой игры.
На карте Байтландии он выбрал n городов, пронумерованых числами от 1 до n , и n - 1 двухстронних дорог, соединяющих эти города. Дороги пронумерованы числами от 1 до n - 1 , i -я дорога имеет длину l i километров и соединяет города с номерами u i и v i . При этом между любой парой выбранных городов существует путь вдоль выбранных дорог. В процессе игры города и дороги оказываются заражены опасной инфекцией. Город может быть полностью заражён или не заражён, а у дороги могут быть заражены некоторые участки.
По задумке Васи в начале игры происходит заражение городов c номерами a 1 , a 2 , ..., a m . Затем инфекция распространяется вдоль прилежащих дорог. Как только она достигает ранее незаражённого города, он становится заражённым. В тот же момент инфекция начинает распространяться по прилежащим к только что заражённому городу дорогам. Заражение города происходит мгновенно, а по дорогам инфекция распространяется с одной и той же скоростью: один километр в минуту.
В каждый момент времени незаражённые города и участки дорог образуют компоненты незаражённой связности . Незаражённый город и незаражённые участки прилежащих к нему дорог всегда находятся в одной компоненте. Два незаражённых города находятся в одной компоненте в том и только в том случае, если между ними существует путь, проходящий по полностью незаражённым дорогам и городам. Компонента незаражённой связности может и вовсе не содержать городов, а только незаражённый участок дороги, которая соединяет уже заражённые города.
Игра заканчивается в тот момент, когда все города и дороги становятся полностью заражёнными. Вася еще не придумал роль игроков в этой игре, но для начала он хочет узнать, какое максимальное количество компонент незаражённой связности будет одновременно существовать в процессе игры.
Первая строка входных данных содержит целое число n — количество выбранных городов ( 2 ≤ n ≤ 10 5 ). Следующие n - 1 строк содержат описание выбранных дорог, i -я строка содержит три целых числа u i , v i и l i — номера городов, соединённых i -й дорогой, и длину этой дороги ( 1 ≤ u i , v i ≤ n ; u i ≠ v i ; 1 ≤ l i ≤ 10 9 ).
Следующая строка содержит целое число m — количество городов, в которых происходит заражение в начале игры ( 1 ≤ m ≤ n ). В следущей строке находятся целые числа a 1 , a 2 , ..., a m — номера этих городов ( 1 ≤ a i ≤ n , все a i различны).
Выведите одно целое число — максимальное количество компонент незаражённой связности, одновременно существующих в процессе игры.
8 1 2 1 1 3 1 2 4 1 2 5 1 3 6 1 3 7 1 1 8 4 2 1 8
5