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

时间限制: 5s 内存限制: 256MB 提交: 5262 解决: 1084
题目描述
某景区一共有 N 个景点,编号 1 到 N。景点之间共有 N − 1 条双向的摆渡车线路相连,形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行,需要花费一定的时间。
小明是这个景区的资深导游,他每天都要按固定顺序带客人游览其中 K 个景点:A1, A2, . . . , AK。今天由于时间原因,小明决定跳过其中一个景点,只带游客按顺序游览其中 K − 1 个景点。具体来说,如果小明选择跳过 Ai,那么他会按顺序带游客游览 A1, A2, . . . , Ai−1, Ai+1, . . . , AK, (1 ≤ i ≤ K)。
请你对任意一个 Ai,计算如果跳过这个景点,小明需要花费多少时间在景点之间的摆渡车上?
输入
第一行包含 2 个整数 N 和 K。
以下 N − 1 行,每行包含 3 个整数 u, v 和 t,代表景点 u 和 v 之间有摆渡车线路,花费 t 个单位时间。
最后一行包含 K 个整数 A1, A2, . . . , AK 代表原定游览线路。
输出
输出 K 个整数,其中第 i 个代表跳过 Ai 之后,花费在摆渡车上的时间。
样例输入
6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 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 ≤ 102
对于 40% 的数据,2 ≤ K ≤ N ≤ 104
对于 100% 的数据,2 ≤ K ≤ N ≤ 105,1 ≤ u, v, Ai ≤ N,1 ≤ t ≤ 105。保证Ai 两两不同。

比赛公告

2023年蓝桥杯比赛大学B组省赛题目以及团队成员皆可参加员无需密码,其他人需要密码进入比赛。