猫咪们狂欢

Problem Description

猫咪们生活在树上。 具体来说，有 $n$ 只猫咪和两棵大小为$n$的树。猫咪编号为 $1 \sim n$ ，每棵树上的节点编号也为 $1 \sim n$ （编号各不相同） 。

• 树：由$n$个点，$n-1$条边构成的连通图，树的大小在这里定义为其节点数。 今晚，每只猫咪要分别选择一棵树，并待在与其编号相同的节点。 在这 $n$ 只猫咪之中，有 $k$ 只猫咪是狂欢猫。狂欢猫晚上不会睡觉，而是会选择开party。其他猫咪则会选择睡觉。 每条树边都有一个狂欢值，如果这条边连接的两个节点在晚上都有狂欢猫待着，这个狂欢值就会被累加到总狂欢值上。 最大化今晚的总狂欢值，并输出这个值。

Input

第一行包含一个正整数 $T(1\leq T\leq 50)$ ，表示测试用例组数。对于每一组测试用例：

• 第一行包含两个正整数 $n$ 和 $k$ ，分别表示猫咪的总数和狂欢猫的数量，$1\leq k\leq n\leq 1000$.
• 接下来一行包含 $k$ 个整数，分别表示狂欢猫的编号，保证这 $k$ 个数互不相等。
• 接下来 $n - 1$ 行，每行包含三个正整数 $u,v$ 和 $w$ ，表示第一棵树的一条连接 $u,v$ 且狂欢值为 $w$ 的边。
• 接下来 $n - 1$ 行，每行包含三个正整数 $u,v$ 和 $w$ ，表示第二棵树的一条连接 $u,v$ 且狂欢值为 $w$ 的边。
• 上述 $w:1\leq w\leq 20$.
• 对所有测试用例，$\sum n \leq 10000$.

Output

共 $T$ 行，每行一个整数分别表示对应测试用例的答案。

Sample Input

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

Sample Output

5
3

Hint

• 第一组数据，狂欢猫 $2,3$ 待在第二棵树上，得到狂欢值 $5$.
• 第二组数据，狂欢猫 $1,2,3$ 待在第一棵树上，得到狂欢值 $2 + 1 = 3$

Source

2024“钉耙编程”中国大学生算法设计超级联赛（5）