All submissions for this problem are available.There are $N$ cities in a country and all the cities are connected in form of a tree. There are $K$ special cities that have treasure hidden in them. Chef is interested to explore these special cities, every city has a portal that takes chef to any city he wants and returns him back to the same city. For example, if chef is in the city $i$ and he wants to explore cities $j$ and $k$, on the 1st day the portal will take chef to city $j$ and after exploring Chef will return back city $i$. On the second day chef will travel to city $k$ through the portal and return back to city $i$. However, travelling through the portals is not free. For a two way trip between city $i$ and city $j$ (travelling from city $i$ to city $j$ and return to city $i$) the portal requires coins equal to the distance between the cities $i$ and $j$. Chef can start from any city he wants. Chef is interested to determine the minimum number of coins he would require to explore the special cities can you help him? ###Input: - The 1st line contains two integers $N$ and $K$, the number of cities and the number of special cities. - The next $N−1$ lines each contain two integers denoting that there is a bi-directional edge between the cities. - The next line contains K space separated integers denoting the special cities. ###Output: A single integer – the minimum number of coins required to explore all special cities. ###Constraints - $1 \leq N \leq 10^6$ - $1 \leq K \leq N$ ###Subtasks - 20 points : $1 \leq N \leq 3000$ - 80 points : $1 \leq N \leq 10^6$ ###Sample Input: 5 2 1 2 1 3 2 4 2 5 3 4 ###Sample Output: 3 ###EXPLANATION: If Chef is starts from city $1$, travelling to city $3$ would require $1$ coin and travelling to city $4$ would require $2$ coins. Hence the answer is $3$.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.