P9808 [POI 2022/2023 R1] zbo

This problem is translated from [POI2022~2023R1 zbo](https://sio2.mimuw.edu.pl/c/oi30-1/p/zbo/)。

In ancient times, there was a king who ruled $n$ villages. These villages were connected by $n - 1$ roads, and the king’s original castle was in village $1$. The king’s sons will soon become adults. As adult princes, they need their own castles, so **new castles** will be built in some villages. Each castle needs to communicate. However, the distances are too large, so each day every castle sends some carrier pigeons to deliver messages to every other castle. A carrier pigeon needs to eat one gram of grain for every kilometer it travels. Please write a program to compute, after each castle is built (in the given input order), the minimum total amount of grain needed so that all castles can communicate. More specifically, let $dis(x,y)$ be the amount of grain needed to travel from $x$ to $y$. After building castle $i$, compute $\sum ^{i} _{x=1} \sum ^{i}_{y=1} dis(x,y)$. Note that in the above formula, the cost for two identical locations is taken to be $0$.

The first line contains two integers $n$ and $k \ (1 \leq k < n \leq 10^5)$, representing the number of villages and the number of new castles to be built. The next $n - 1$ lines each contain three integers $a,b,c \ (1 \leq a,b \leq n, a \neq b, 1 \leq c \leq 1000)$, indicating that there is an undirected edge of length $c$ between $a$ and $b$. The next $k$ lines each contain one integer $d_{i}$, meaning that the $i$-th castle is built at village $d_{i}$. Note that no two castles are built at the same village.

For each built castle, output the minimum total cost.

The subtasks are as follows: | Subtask ID | Special property | Score | | :----------: | :----------: | :----------: | | $1$ | $n \cdot k \leq 10^5$ | $15$ | | $2$ | The villages form a chain from $1$ to $n$ | $35$ | | $3$ | No special property | $50$ | In this problem, subtask $0$ is the sample. Translated by ChatGPT 5