{"problem":{"name":"[蓝桥杯 2023 省 B] 景区导游","description":{"content":"某景区一共有 $N$ 个景点，编号 $1$ 到 $N$。景点之间共有 $N-1$ 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。 小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 $K$ 个景点：$A_{1},A_{2},\\ldots,A_{K}$。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 $K-1$ 个","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9245"},"statements":[{"statement_type":"Markdown","content":"某景区一共有 $N$ 个景点，编号 $1$ 到 $N$。景点之间共有 $N-1$ 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。\n\n小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 $K$ 个景点：$A_{1},A_{2},\\ldots,A_{K}$。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 $K-1$ 个景点。具体来说，如果小明选择跳过 $A_{i}$，那么他会按顺序带游客游览 $A_{1},A_{2},\\ldots,A_{i-1},A_{i+1},\\ldots,A_{K}(1 \\leq i \\leq K)$。\n\n请你对任意一个 $A_{i}$，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？\n\n## Input\n\n第一行包含 $2$ 个整数 $N$ 和 $K$。\n\n以下 $N-1$ 行，每行包含 $3$ 个整数 $u，v, t$，代表景点 $u$ 和 $v$ 之间有摆渡车线路，花费 $t$ 个单位时间。\n\n最后一行包含 $K$ 个整数 $A_{1},A_{2},\\ldots,A_{K}$ 代表原定游览线路。\n\n## Output\n\n输出 $K$ 个整数，其中第 $i$ 个代表跳过 $A_{i}$ 之后，花费在摆渡车上的时间。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n原路线是 $2 \\rightarrow 6 \\rightarrow 5 \\rightarrow 1$。\n\n当跳过 $2$ 时，路线是 $6 \\rightarrow 5 \\rightarrow 1$，其中 $6 \\rightarrow 5$ 花费时间 $3+2+2=7$，$5 \\rightarrow 1$ 花费时间 $2+1=3$，总时间花费 $10$。\n\n当跳过 $6$ 时，路线是 $2 \\rightarrow 5 \\rightarrow 1$，其中 $2 \\rightarrow 5$ 花费时间 $1+1+2=4$，$5 \\rightarrow 1$ 花费时间 $2+1=3$，总时间花费 $7$。\n\n当跳过 $5$ 时，路线是 $2 \\rightarrow 6 \\rightarrow 1$，其中 $2 \\rightarrow 6$ 花费时间 $1+1+2+3=7$，$6 \\rightarrow 1$ 花费时间 $3+2+1=6$ ，总时间花费 $13$。\n\n当跳过 $1$ 时，路线时 $2 \\rightarrow 6 \\rightarrow 5$，其中 $2 \\rightarrow 6$ 花费时间 $1+1+2+3=7$，$6 \\rightarrow 5$ 花费时间 $3+2+2=7$ ，总时间花费 $14$。\n\n**【评测用例规模与约定】**\n\n对于 $20 \\%$ 的数据，$2 \\leq K \\leq N \\leq 100$。\n\n对于 $40 \\%$ 的数据，$2 \\leq K \\leq N \\leq 10^{4}$。\n\n对于 $100 \\%$ 的数据，$2 \\leq K \\leq N \\leq 10^{5}$，$1 \\leq u,v,A_{i} \\leq N$，$1 \\leq t \\leq 10^{5}$。保证 $A_{i}$ 两两不同。 \n\n蓝桥杯 2023 省赛 B 组 I 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9245","tags":["2023","最近公共祖先 LCA","蓝桥杯省赛"],"sample_group":[["6 4\n1 2 1\n1 3 1\n3 4 2\n3 5 2\n4 6 3\n2 6 5 1","10 7 13 14\n"]],"created_at":"2026-03-03 11:09:25"}}