P9808 [POI 2022/2023 R1] zbo

题目译自 [POI2022~2023R1 zbo](https://sio2.mimuw.edu.pl/c/oi30-1/p/zbo/)。

远古时期有一个国王，他统治了 $n$ 个村庄，这些村庄以 $n-1$ 条道路连接，原来的国王城堡在 $1$ 号村庄。 国王的儿子不久就要成年了，作为成年的王子们，其需要自己的城堡，所以在一些村庄会有**新的城堡**。 每座城堡都需要进行通讯，但是无奈距离太过遥远，为此，每个城堡每天都会派出若干个信鸽，向其他每个城堡发送消息。一只信鸽每行驶一公里就要吃一克谷物。 请你实现一个程序，求出按照输入顺序建造的每个城堡建造完之后所有城堡都能通讯的最少花费谷物数量。 具体的，定义 $dis(x,y)$ 为 $x$ 到 $y$ 所花费的谷物数，求每个城堡 $i$ 建造完后的 $\sum ^{i} _{x=1} \sum ^{i}_{y=1} dis(x,y)$。 注意上述式子默认两个相同的地点所花费为 $0$。

输入第一行两个数字 $n$ 和 $k \ (1 \leq k < n \leq 10^5)$，分别表示村庄数量和即将建造的城堡数量。 接下来 $n-1$ 行，每行三个整数 $a,b,c \ (1 \leq a,b \leq n, a \neq b, 1 \leq c \leq 1000)$，表示 $a$ 到 $b$ 存在一条长度为 $c$ 的无向边。 再接下来 $k$ 行，每行一个整数 $d_{i}$，表示第 $i$ 个城堡建设在 $d_{i}$ 位置上，注意城堡不会重复建在一个位置。

对于每个建造完的城堡，输出最小花费。

子任务分配如下： | 子任务编号 | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | $1$ | $n \cdot k \leq 10^5$ | $15$ | | $2$ | 村庄是一条从 $1$ 到 $n$ 的链 | $35$ | | $3$ | 无特殊性质 | $50$ | 本题中，子任务 $0$ 为样例。