题目描述
给定一个包含 n 个节点的树,其中 m 个节点存在传送门,当飞船经过存在传送门的节点时,可以选择无消耗地传送至其他存在传送门的节点。
现在有 q 个飞船将从 si 节点出发前往 ti 节点,每艘飞船在飞行中至多可以进行一次传送,对于每艘飞船请输出其所有路径中的最小边权和。
输入
第一行包含两个整数 n,m (1<=m<=n<=2*10^5) ,表示树的大小和存在传送门的节点总数。
第二行包含 m 个整数,表示存在传送门的节点。
接下来 n-1 行,每行包括三个整数 u,v,w (1<=u,v<=n, u!=v, 1<=w<=10^9) ,表示 u 节点与 v 节点之间存在一条边权为 w 的边。
接下来一行包含一个整数 q (1<=q<=2*10^5) ,表示飞船的数量,接下来 q 行每行包含两个整数 si,ti (1<=si,ti<=n) 表示飞船的出发点和目的地。
输出
共 q 行,对于每艘飞船输出其所有路径中的最小边权和。
7 2
1 5
1 2 8
1 3 1
1 5 7
2 4 8
5 6 3
5 7 1
3
1 6
7 2
1 3
样例输出 Cop
提示
对于第一次询问,最小边权和的路径如下:飞船从 1 节点传送到 5 节点,然后经过 5 节点与 6 节点的连边到达 6 节点,答案为 3 。
对于第二次询问,最小边权和的路径如下:飞船经过 7 节点与 5 节点的连边到达 6 节点,然后从 5 节点传送到 1 节点,再经过 1 节点与 2 节点的连边到达 2 节点,答案为 9 。
对于第三次询问,最小边权和的路径如下:飞船经过 1 节点与 3 节点的连边到达 3 节点,答案为 1 。