景区导游

题目描述

某景区一共有 $N$ 个景点，编号 $1$ 到 $N$。景点之间共有 $N − 1$ 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。 小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 $K$ 个景点：$A_1, A_2, . . . , A_K$。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 $K − 1$ 个景点。具体来说，如果小明选择跳过 $A_i$，那么他会按顺序带游客游览 $A_1, A_2, . . . , A_{i−1}, A_{i+1}, . . . , A_K,$ $(1 ≤ i ≤ K)$。 请你对任意一个 $A_i$，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

输入格式

第一行包含 $2$ 个整数 $N$ 和 $K$。 以下 $N − 1$ 行，每行包含 $3$ 个整数 $u, v$ 和 $t$，代表景点 $u$ 和 $v$ 之间有摆渡车线路，花费 $t$ 个单位时间。 最后一行包含 $K$ 个整数 $A_1, A_2, . . . , A_K$ 代表原定游览线路。

输出格式

输出 $K$ 个整数，其中第 $i$ 个代表跳过 $A_i$ 之后，花费在摆渡车上的时间。

样例 #1

样例输入 #1

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

样例输出 #1

10 7 13 14

提示

原路线是 $2 → 6 → 5 → 1$。 当跳过 $2$ 时，路线是 $6 → 5 → 1$，其中 $6 → 5$ 花费时间 $3 + 2 + 2 = 7，5 → 1$ 花费时间 $2 + 1 = 3$，总时间花费 $10$。 当跳过 $6$ 时，路线是 $2 → 5 → 1$，其中 $2 → 5$ 花费时间 $1 + 1 + 2 = 4$，$5 → 1$ 花费时间 $2 + 1 = 3$，总时间花费 $7$。 当跳过 $5$ 时，路线是 $2 → 6 → 1$，其中 $2 → 6$ 花费时间 $1 + 1 + 2 + 3 = 7，6 → 1$ 花费时间 $3 + 2 + 1 = 6$，总时间花费 $13$。 当跳过 $1$ 时，路线时 $2 → 6 → 5$，其中 $2 → 6$ 花费时间 $1 + 1 + 2 + 3 = 7，6 → 5$ 花费时间 $3 + 2 + 2 = 7$，总时间花费 $14$。

对于 $20\%$ 的数据，$2 ≤ K ≤ N ≤ 10^2$。 对于 $40\%$ 的数据，$2 ≤ K ≤ N ≤ 10^4$。 对于 $100\%$ 的数据，$2 ≤ K ≤ N ≤ 10^5，1 ≤ u, v, A_i ≤ N，1 ≤ t ≤ 10^5$。保证$A_i$ 两两不同。