配点 : 700 点
問題文
N 有一棵由顶点组成的树,顶点被 1 它们的编号最大为 N 标有直到……的编号。N-1 条边中 i 第一条边是顶点 A_i 和 B_i 的权重为 V_i 以双向连接。
X 只 Tapi酱 和 Y 只 Tapu酱。最初。 j 第 个 Tapi酱 位于顶点 P_j、k 第 个 Tapu酱 位于顶点 Q_k 。同一顶点上不存在多个 Tapi酱或 Tapu酱。
所有 Tapi酱都可以重复执行移动到相邻顶点的操作。但是 Tapi酱和 Tapu酱关系不好。如果 Tapi酱移动到 Tapu酱所在的顶点,可能会感到不愉快。
因此,希望通过删除若干条边,使所有 Tapi酱都无法移动到 Tapu酱所在的顶点。此时,请求出要删除的边的权重总和的最小值。
制約
- 2 \leq N \leq 5 \times 10^5
- 1 \leq X, Y \leq N
- 1 \leq A_i \lt B_i \leq N
- 1 \leq V_i \leq 10^9
- 1 \leq P_j, Q_k \leq N
- P_1, P_2, ..., P_X, Q_1, Q_2, ..., Q_Y 是互不相同的
- 给出的图是树
- 所有输入均为整数
部分点
- N \leq 500 对于满足条件的数据集求得正确答案时,40 点。
入力
输入是按以下格式从标准输入给出的。
N X Y
A_1 B_1 V_1
A_2 B_2 V_2
:
A_{N-1} B_{N-1} V_{N-1}
P_1 P_2 ... P_X
Q_1 Q_2 ... Q_Y
出力
1 行输出答案。
入力例 1
5 4 1 1 2 1 2 3 2 3 4 3 4 5 4 1 2 4 5 3
出力例 1
5
2 第 个和 3 删除第...条边。此时,任何塔皮酱都不能移动到有塔普酱的顶点 3 不能移动到。
入力例 2
6 2 2 1 2 6 1 3 3 1 4 4 3 5 2 3 6 2 1 2 5 6
出力例 2
3
2 删除第...条边。