该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

谷物消耗

题目描述

Y 同学是三金国的国王。王国中有 $n$ 座城市，由 $n-1$ 条双向道路连接，形成了一棵树的结构。城市从 $1$ 到 $n$ 编号。国王 Y 同学的城堡建在 $1$ 号城市。

Y 同学有 $k$ 位王子，他们即将成年。按照王国的传统，每位成年的王子都需要一座自己的城堡。因此，Y 同学计划在 $k$ 个不同的城市为王子们建造新的城堡。

国王和王子们需要保持密切的联系，以处理王国的各类事务。为此，每天每座城堡都会向所有其他城堡各派遣一名信使传递信息。也就是说，对于任意两座不同的城堡 A 和 B，都会有一名信使从 A 前往 B，同时另一名信使从 B 前往 A。

信使的坐骑在每次出发前都需要补充能量。具体来说，每走 $1$ 公里的路，坐骑需要消耗 $1$ 单位的谷物。

随着王子们的城堡一座接一座地建成，王国每日消耗的谷物总量也在不断变化。最初，王国中只有位于 $1$ 号城市的国王城堡。接着，$k$ 位王子将按给定的顺序，依次在指定的城市建造他们的城堡。

请你编写一个程序，计算出每当一座新的王子城堡建成后，整个王国用于信使交通的每日谷物总消耗量。

输入格式

第一行包含两个整数 $n, k$，分别表示王国的城市数量和王子的数量。

接下来 $n-1$ 行，每行包含三个整数 $u, v, w$，表示城市 $u$ 和城市 $v$ 之间有一条长度为 $w$ 公里的双向道路。

接下来 $k$ 行，每行包含一个整数 $d$，表示下一位王子将要在城市 $d$ 建造城堡。保证所有 $d$ 各不相同，且不为 $1$。

输出格式

输出 $k$ 行。第 $i$ 行（$1 \le i \le k$）输出一个整数，表示第 $i$ 位王子的城堡建成后，王国每日的谷物总消耗量。

样例

样例输入

5 3
1 4 3
3 1 6
1 2 5
4 5 1
5
3
2

样例输出

8
40
90

提示

样例解释

初始时，只有国王的城堡在城市 $1$。

1. 第一位王子在城市 $5$ 建造城堡。

   • 此时城堡集合为 $\{1, 5\}$。
   • 需要计算 1 -> 5 和 5 -> 1 的路程。
   • 城市 $1$ 和 $5$ 之间的最短距离为 $\text{dist}(1, 5) = \text{dist}(1, 4) + \text{dist}(4, 5) = 3 + 1 = 4$。
   • 总消耗为 $\text{dist}(1, 5) + \text{dist}(5, 1) = 2 \times 4 = 8$。

2. 第二位王子在城市 $3$ 建造城堡。

   • 此时城堡集合为 $\{1, 5, 3\}$。
   • 需要计算所有有序点对 $(1,5), (5,1), (1,3), (3,1), (5,3), (3,5)$ 的路程。
   • 总消耗为 $2 \times (\text{dist}(1, 5) + \text{dist}(1, 3) + \text{dist}(5, 3))$。
   • $\text{dist}(1, 5) = 4$。
   • $\text{dist}(1, 3) = 6$。
   • $\text{dist}(5, 3) = \text{dist}(5, 4) + \text{dist}(4, 1) + \text{dist}(1, 3) = 1 + 3 + 6 = 10$。
   • 总消耗为 $2 \times (4 + 6 + 10) = 2 \times 20 = 40$。

3. 第三位王子在城市 $2$ 建造城堡。

   • 此时城堡集合为 $\{1, 5, 3, 2\}$。
   • 总消耗为 $2 \times (\text{dist}(1,5) + \text{dist}(1,3) + \text{dist}(1,2) + \text{dist}(5,3) + \text{dist}(5,2) + \text{dist}(3,2))$。
   • $\text{dist}(1, 5) = 4$, $\text{dist}(1, 3) = 6$, $\text{dist}(1, 2) = 5$, $\text{dist}(5, 3) = 10$。
   • $\text{dist}(5, 2) = \text{dist}(5, 4) + \text{dist}(4, 1) + \text{dist}(1, 2) = 1 + 3 + 5 = 9$。
   • $\text{dist}(3, 2) = \text{dist}(3, 1) + \text{dist}(1, 2) = 6 + 5 = 11$。
   • 总消耗为 $2 \times (4 + 6 + 5 + 10 + 9 + 11) = 2 \times 45 = 90$。

数据范围与约定

• 对于所有测试数据，保证 $1 \le k < n \le 10^5$。
• 对于描述道路的 $n-1$ 行，保证 $1 \le u, v \le n$，$u \ne v$，$1 \le w \le 1000$。
• 对于描述新建城堡的 $k$ 行，保证 $2 \le d \le n$。
• 保证给定的 $n-1$ 条道路构成一棵树。
• 保证给定的 $k$ 个建造城堡的城市 $d$ 互不相同。

数据范围