P2700 Eliminate Them One by One

On the Pingjin battlefield of the three major campaigns, the Fu Zuoyi group deployed a long, thin defensive line centered on Beiping and Tianjin, stretching from Tangshan in the east to Zhangjiakou in the west along the railway. They planned to flee south by sea or retreat westward in case of collapse. To annihilate the enemy in place and prevent their escape, the commander formulated a strategy to first cut off the enemy’s retreat routes at both ends and then eliminate them one by one. Following the strategic thinking of a great military leader, as a wise corps commander, you encounter a similar battlefield situation.

There are $N$ cities, among which $K$ are occupied by enemy corps. There are $N - 1$ roads connecting the $N$ cities. The cost to destroy any given road is known. You are given the $K$ cities occupied by the enemy and the destruction cost of every road. Please compute the minimum total cost to isolate these $K$ enemy corps from each other, so that in the second step they can be eliminated one by one.

- The first line contains two positive integers $N$ and $K$. - The second line contains $K$ integers, indicating which cities are occupied by the enemy. - The next $N - 1$ lines each contain three positive integers $a, b, c$, indicating there is a road between city $a$ and city $b$, and the cost to destroy it is $c$. City indices start from $0$.

Output a single line with one integer, the minimum total cost.

Constraints: - For $10\%$ of the testdata, $N \le 10$. - For $100\%$ of the testdata, $2 \le N \le 10^5$, $2 \le K \le N$, $1 \le c \le 10^6$. Translated by ChatGPT 5