アメカーの部屋

时空限制#

C/C++：4s / 1024MB

其他语言：8s / 1024MB

题目背景#

「一条世界线上会有无限的分枝，每条分枝都会通往一个平行世界。」

「这些分枝如同樱花树的枝丫，点缀着无数樱花。」

「这些樱花究竟是盛开的，含苞待放的，还是枯萎的呢？」

「阿良良木只是一位时间的旅人，能做得到的只有『观测』和『转移』。」

「收下来自『你』的电报吧，名侦探。你这条分枝是最后的希望了。」

阿良良木是平行世界的观测者。为了完成使命，她需要将其他平行世界中风见司的电报，转交给最后一条分枝上的司。

题目描述#

错综复杂的世界线可以看作一棵樱花树¹。树上共有 $n$ 个节点，编号为 $1$ 到 $n$。阿良良木一开始位于节点 $s$，她需要到达节点 $t$。

阿良良木在旅途中会处于两种状态之一：观测状态 或 转移状态。

每条边连接两个节点 $u, v$，并拥有两个代价 $a, b$：

• 当阿良良木处于 观测状态 时，沿这条边移动的代价为 $a$；
• 当阿良良木处于 转移状态 时，沿这条边移动的代价为 $b$。

树上有 $k$ 个特殊节点，这些节点被称为 樱点。

当阿良良木位于某个樱点时，她可以在 观测状态 与 转移状态 之间切换，切换不需要任何代价，且可以在同一个樱点切换任意多次。

阿良良木初始处于 观测状态，最终到达节点 $t$ 时，她可以处于任意状态。

为了保存力量，阿良良木需要知道从节点 $s$ 到达节点 $t$ 所需要的最小总代价。

输入格式#

每个测试包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

对于每组测试用例：

• 第一行包含四个整数 $n, k, s, t$ ($2 \le n \le 2 \times 10^5$，$1 \le k \le n$，$1 \le s,t \le n$，$s \ne t$)，分别表示树的节点数、樱点数量、起点和终点。

• 第二行包含 $k$ 个互不相同的整数 $p_1, p_2, \dots, p_k$ ($1 \le p_i \le n$)，表示所有樱点的编号。

• 接下来 $n-1$ 行，每行包含四个整数 $u, v, a, b$ ($1 \le u,v \le n$，$1 \le a,b \le 10^9$)，表示节点 $u$ 和节点 $v$ 之间有一条边、观测状态时移动的代价和转移状态时移动的代价。

保证每组测试用例给出的图都是一棵树。

保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$。

输出格式#

对于每组测试用例，输出一行一个整数，表示从节点 $s$ 到达节点 $t$ 的最小总代价。

样例#

1
3
2
3 1 1 3
3
2
4
1 2 1 4
5
2 3 3 2
6
4 2 4 3
7
1 4
8
1 2 2 4
9
2 3 3 5
10
2 4 1 3
11
5 1 1 5
12
3
13
1 2 2 3
14
2 3 2 1
15
2 4 100 1
16
4 5 100 1

1
3
2
4
3
7

说明/提示#

在第一个测试用例中，一种最优方案为 $1 \to 2 \to 3$。在节点 $2$ 切换到转移状态后，总代价为 $1+2=3$。

在第三个测试用例中，一种最优方案为 $1 \to 2 \to 3 \to 2 \to 4 \to 5$。在节点 $3$ 切换到转移状态后，总代价为 $2+2+1+1+1=7$。