问题2537--绿绿学姐与AI 2

2537: 绿绿学姐与AI 2

时间限制: 1 Sec  内存限制: 128 MB
提交: 23  解决: 9
[状态] [讨论版] [提交] [命题人:]
题目描述
大事不好啦!绿绿学姐的深度学习程序BetaMao成精啦!BetaMao即将攻陷网络中心!工大的网络正面临瘫痪的危机!为了拯救工大的网络,九位ACM组的成员站了出来,他们能做的就是————写个程序!
工大的网络拓扑可以看成由n个节点组成的一棵树,节点的编号为1~n,树的根节点网络中心位于1号节点,网络中心可以通过一些边到达其他所有点,其他所有点也可以通过一些边到达网络中心。
现在绿绿的AI已经攻占了k个节点,为了阻止AI攻占网络中心,唯一的措施是拔掉一些网线,在网络拓扑中的结果就是删掉一些边,使得被攻占的节点无法联通网络中心。
然而网线分布十分散乱,有的在院长办公室,有的在系办,所以拔掉网线的代价也不一样。
拔掉网线的方案有很多种,校长要求得到代价最小的一种方案,九位成员正在急速的敲代码,然而他们进展十分缓慢,你决定帮助他们写完这个程序。
问题解决之后怎么办?当然是选择原谅绿绿学姐啦!
输入
一个整数T(<=20),表示测试数据的组数。
每组数据第一行是两个整数n(2<=n<=100000),k(1<=k<n),表示网络拓扑中节点的个数和被攻占的节点个数。
第二行是k个整数,表示被攻占的节点的编号,保证网络中心没有被攻占。
随后n-1行每行三个整数a,b,c表示节点a和节点b之间有一条代价为c(<=1000000000)的边,保证数据是一颗合法的树。
输出
一个整数,通过拔网线使得所有被攻占的节点都无法联通网络中心的最小的代价。
样例输入 Copy
1
6 3
3 4 5
1 2 100
2 4 1
2 5 1
1 3 1
3 6 100
样例输出 Copy
3
来源/分类