蓝桥杯2023年第十四届省赛真题-景区导游

某景区一共有 N 个景点，编号 1 到 N。景点之间共有 N − 1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。

小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K 个景点：A₁, A₂, . . . , A_K。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K − 1 个景点。具体来说，如果小明选择跳过 Ai，那么他会按顺序带游客游览 A₁, A₂, . . . , 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₁, A₂, . . . , A_K 代表原定游览线路。

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

原路线是 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。

对于 20% 的数据，2 ≤ K ≤ N ≤ 10²。

对于 40% 的数据，2 ≤ K ≤ N ≤ 10⁴。

对于 100% 的数据，2 ≤ K ≤ N ≤ 10⁵，1 ≤ u, v, A_i ≤ N，1 ≤ t ≤ 10⁵。保证A_i 两两不同。