问题 D: 剪切

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:0

题目描述

Soyo 的女儿由于人格分裂正在休学,因此 Soyo 需要帮她女儿照顾在学校种的小黄瓜。

喜报:Soyo 的女儿人格分裂好了(?),现在改种苦瓜了,所有的黄瓜都不需要了。

题目描述

Soyo 有一棵具有 nn 个节点的黄瓜树,树上第 ii 个节点上有一根编号为 ii ,美丽指数为 aiai 的黄瓜。

Soyo 非常喜欢其中的 mm 根黄瓜,并且她需要删除一些节点将树变成 mm 个连通块,使得每个连通块恰好有一根她喜欢的黄瓜。

Soyo 想知道所有未被删除的节点中黄瓜的美丽指数之和的最大值是多少,若无解则输出 -1。

输入格式

第一行输入一个整数 T(1≤T≤105)T1T105 ,表示测试样例数量。

每组测试样例:

第一行输入两个整数 n,m(1≤m≤n≤2×105)n,m1mn2×105 ,表示树的节点个数和 Soyo 喜欢的黄瓜数量。

第二行输入 nn 个整数 ai(1≤ai≤109)ai1ai109 ,表示第 ii 根黄瓜的美丽指数。

接下来 n−1n1 行,每行输入两个整数 u,v(1≤u,v≤n)u,v1u,vn ,表示树上的边。

最后一行输入 mm 个整数 bi(1≤bi≤n)bi1bin ,表示 Soyo 喜欢的黄瓜编号,数据保证所有的 bibi 互不相同。

数据保证: ∑n≤2×106n2×106 。

输出格式

对于每组数据,在一行中输出一个整数表示答案。

输入样例 复制

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

输出样例 复制

8
-1

数据范围与提示

对于第1组样例:

最优解是删除第 2 个节点,剩余三个节点的黄瓜美丽指数之和为 1 + 3 + 4 = 8 。