Pandemic 2
Time limit1sMemory limit512 MB
On a weighted tree where some vertices start infected and the infection spreads along edges at speed one, find the maximum number of uninfected connected components that ever exist at one moment.
Statement
Vasya's friends always play the same board game, called "Pandemic". Vasya is tired of it, so he decided to make his own version.
He chooses cities on the map of Byteland and bidirectional roads connecting them. The cities are numbered to , and the roads are numbered to . The -th road has length kilometers and connects cities and . There is a path along the roads between any pair of cities. As the game goes on, roads and cities become infected. A city is either entirely infected or not infected at all, and a road can have both infected and uninfected parts.
At the start of the game, cities become infected. The infection then spreads along the adjacent roads. A city becomes infected the moment the infection reaches it. At the same time, the infection starts spreading along the roads adjacent to the city that has just been infected. The city becomes infected instantly, and the infection spreads along any road at a constant speed of one kilometer per minute.
At every moment of the game, the still uninfected cities and road parts form uninfected connected components. An uninfected city and the adjacent uninfected road parts always lie in the same component. Two uninfected cities lie in the same component if and only if a path of uninfected roads connects them. An uninfected connected component can contain no cities at all, in which case it consists of a single uninfected road part connecting already infected cities.
The game ends when all cities and roads are infected. Vasya has not decided the roles of the players yet, but first he wants to know the maximum number of uninfected connected components that can exist on the board at some moment of the game.
Input
The first line contains one integer , the number of chosen cities (). The next lines describe the chosen roads; the -th of them contains three integers , , : the cities joined by the -th road and its length (; ; ).
The next line contains one integer , the number of cities infected at the start of the game (). The next line contains , the numbers of these cities (, all distinct).
Output
Print one integer: the maximum number of uninfected connected components on the board at some moment of the game.