This page is still under construction.

Parts of this page are still being built. What you see may change.

Pandemic 2

Time limit1sMemory limit512 MB

Summary
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.
Level

Hard8 of 10

Topics
Tree, DFS, Sorting, Greedy
Solved
No attempts yet

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 nn cities on the map of Byteland and n−1n-1 bidirectional roads connecting them. The cities are numbered 11 to nn, and the roads are numbered 11 to n−1n-1. The ii-th road has length lil_i kilometers and connects cities uiu_i and viv_i. 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 a1,a2,…,ama_1, a_2, \ldots, a_m 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 nn, the number of chosen cities (2≤n≤1052 \le n \le 10^5). The next n−1n-1 lines describe the chosen roads; the ii-th of them contains three integers uiu_i, viv_i, lil_i: the cities joined by the ii-th road and its length (1≤ui,vi≤n1 \le u_i, v_i \le n; ui≠viu_i \ne v_i; 1≤li≤1091 \le l_i \le 10^9).

The next line contains one integer mm, the number of cities infected at the start of the game (1≤m≤n1 \le m \le n). The next line contains a1,a2,…,ama_1, a_2, \ldots, a_m, the numbers of these cities (1≤ai≤n1 \le a_i \le n, all aia_i distinct).

Output

Print one integer: the maximum number of uninfected connected components on the board at some moment of the game.

Examples1

  1. Example 1

    Input
    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
    
    Expected output
    5