P1084 [NOIP 2012 Senior] Epidemic Control

Country H has $n$ cities. These $n$ cities are connected by $n-1$ bidirectional roads to form a tree. City $1$ is the capital and is the root of the tree. A highly dangerous contagious disease has broken out in the capital. To control the epidemic and prevent it from spreading to border cities (cities represented by leaf nodes), the authorities decide to deploy the army to set up checkpoints in some cities so that every path from the capital to any border city contains at least one checkpoint. Checkpoints may also be set in border cities. Note in particular that no checkpoint may be set in the capital. Currently, troops are already stationed in some cities of Country H, and multiple troops may be stationed in the same city. A troop can move between adjacent cities along roads and can set up a checkpoint in any city except the capital. Each troop can set a checkpoint in only one city. The time for a troop to move across a road from one city to another equals the length of that road (unit: hours). What is the minimum number of hours needed to control the epidemic? Note that different troops can move simultaneously.

The first line contains an integer $n$, the number of cities. The next $n-1$ lines each contain $3$ integers, $u, v, w$, separated by single spaces, indicating there is a road of length $w$ between cities $u$ and $v$. It is guaranteed that the input forms a tree, and the root is city $1$. The next line contains an integer $m$, the number of troops. The next line contains $m$ integers, separated by single spaces, indicating the cities where the $m$ troops are stationed.

Output a single integer, the minimum time needed to control the epidemic. If it is impossible to control the epidemic, output $-1$.

Sample explanation: The first troop sets a checkpoint at city $2$, and the second troop moves from city $2$ to city $3$ to set a checkpoint. The time needed is $3$ hours. Constraints: It is guaranteed that no troop is stationed in the capital. - For $20\%$ of the testdata, $2 \le n \le 10$. - For $40\%$ of the testdata, $2 \le n \le 50$, $0 < w < 10^5$. - For $60\%$ of the testdata, $2 \le n \le 1000$, $0 < w < 10^6$. - For $80\%$ of the testdata, $2 \le n \le 10^4$. - For $100\%$ of the testdata, $2 \le m \le n \le 5 \times 10^4$, $0 < w < 10^9$. NOIP 2012 Senior Day 2, Problem 3. Translated by ChatGPT 5