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

题目描述

园区里有 $n$ 个地点，编号为 $1,2,\ldots,n$．地点之间有 $n-1$ 条双向道路，构成一棵树．每条道路都有一个正整数长度．

巡检员从 $1$ 号地点出发，需要到达任务清单上的 $k$ 个地点．他可以自行安排顺序，可以重复经过道路和地点，完成任务后可以在任意地点结束，不必回到 $1$ 号地点．路线长度等于每次经过的道路长度之和，同一条道路经过多次就计算多次．

现在有 $k$ 个独立的调整方案．第 $i$ 个方案仅取消清单上地点 $x_i$ 的巡检任务，其余 $k-1$ 个任务仍须完成．取消任务不会关闭地点或道路，巡检员仍可以经过 $x_i$．

请分别求出每个调整方案下，完成剩余任务所需的最短路线长度．不同方案互不影响，任务不会累计取消．如果没有剩余任务，可以不移动，路线长度为 $0$．

输入格式

第一行输入两个整数 $n,k$，分别表示地点数和任务数．

接下来 $n-1$ 行，每行输入三个整数 $u,v,w$，表示地点 $u,v$ 之间有一条长度为 $w$ 的双向道路．

最后一行输入 $k$ 个互不相同的整数 $x_1,x_2,\ldots,x_k$，表示任务清单．

输出格式

输出 $k$ 行，第 $i$ 行表示仅取消地点 $x_i$ 的任务时，完成其余任务所需的最短路线长度．

样例 1

输入

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

输出

12
16
7

解释

取消地点 $3$ 的任务时，可以沿 $1\to2\to4\to2\to1\to5\to6$ 行走，长度为 $12$．

取消地点 $4$ 的任务时，可以沿 $1\to2\to3\to2\to1\to5\to6$ 行走，长度为 $16$．

取消地点 $6$ 的任务时，可以沿 $1\to2\to4\to2\to3$ 行走，长度为 $7$．

样例 2

输入

3 2
1 2 2
2 3 5
2 3

输出

7
2

解释

取消地点 $2$ 的任务后，仍需经过地点 $2$ 才能到达地点 $3$．取消的是任务，不是地点．

样例 3

输入

1 1
1

输出

0

数据范围

对于所有数据，保证 $1\le k\le n\le2\times10^5$，$1\le u,v,x_i\le n$，$1\le w\le10^9$．给出的道路构成一棵树，$x_1,x_2,\ldots,x_k$ 互不相同．任务清单可以包含地点 $1$．

本题采用捆绑测试，各子任务相互独立．

下发样例

• Data/sample1.in 与 Data/sample1.ans：题面中的样例 1．
• Data/sample2.in 与 Data/sample2.ans：题面中的样例 2．
• Data/sample3.in 与 Data/sample3.ans：题面中的样例 3．
• Data/sample4.in 与 Data/sample4.ans：满足子任务 1 的附加限制．
• Data/sample5.in 与 Data/sample5.ans：满足子任务 2 的附加限制．
• Data/sample6.in 与 Data/sample6.ans：满足子任务 3 的附加限制．
• Data/sample7.in 与 Data/sample7.ans：满足子任务 4 的附加限制．
• Data/sample8.in 与 Data/sample8.ans：该样例无特殊限制．
• Data/sample9.in 与 Data/sample9.ans：该样例无特殊限制．

大样例下载

点击下载本题选手目录