P6419 [COCI 2014/2015 #1] Kamp

There is a tree with $n$ nodes and $n-1$ edges. Passing through each edge costs a certain amount of time, and any two nodes are connected. There are $K$ people (located at $K$ different nodes) who want to gather at one node for a party. After the party ends, a car needs to start from the party node, pick up all people into the car, and then send these $K$ people back to their respective homes. Please answer: for $i = 1 \sim n$, if the party is held at node $i$, what is the minimum time the driver needs to send all $K$ people back home.

The first line contains two integers $n, K$. The next $n-1$ lines each contain three numbers $x, y, z$, meaning there is an edge between $x$ and $y$ that costs $z$ time. The next $K$ lines each contain one number, indicating the locations of the $K$ people.

Output $n$ numbers. The number on line $i$ means: if the party is held at node $i$, the minimum time the driver needs.

#### Constraints - For $50\%$ of the testdata, $n \le 2 \times 10^3$. - For $100\%$ of the testdata, $1 \le K \le n \le 5 \times 10^5$, $1 \le x, y \le n$, $1 \le z \le 10^8$. Translated by ChatGPT 5