Soyo 的女儿由于人格分裂正在休学,因此 Soyo 需要帮她女儿照顾在学校种的小黄瓜。
喜报:Soyo 的女儿人格分裂好了(?),现在改种苦瓜了,所有的黄瓜都不需要了。
题目描述
Soyo 有一棵具有 nn 个节点的黄瓜树,树上第 ii 个节点上有一根编号为 ii ,美丽指数为 aiai 的黄瓜。
Soyo 非常喜欢其中的 mm 根黄瓜,并且她需要删除一些节点将树变成 mm 个连通块,使得每个连通块恰好有一根她喜欢的黄瓜。
Soyo 想知道所有未被删除的节点中黄瓜的美丽指数之和的最大值是多少,若无解则输出 -1。
第一行输入一个整数 T(1≤T≤105)T(1≤T≤105) ,表示测试样例数量。
每组测试样例:
第一行输入两个整数 n,m(1≤m≤n≤2×105)n,m(1≤m≤n≤2×105) ,表示树的节点个数和 Soyo 喜欢的黄瓜数量。
第二行输入 nn 个整数 ai(1≤ai≤109)ai(1≤ai≤109) ,表示第 ii 根黄瓜的美丽指数。
接下来 n−1n−1 行,每行输入两个整数 u,v(1≤u,v≤n)u,v(1≤u,v≤n) ,表示树上的边。
最后一行输入 mm 个整数 bi(1≤bi≤n)bi(1≤bi≤n) ,表示 Soyo 喜欢的黄瓜编号,数据保证所有的 bibi 互不相同。
数据保证: ∑n≤2×106∑n≤2×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 。