双向生成树

Question

我在interviewstreet.com上遇到了这个问题

机器再一次袭击了Xions王国.Xions王国有N个城市和N-1双向道路.道路网络使得任何一对城市之间都有一条独特的道路.

Morpheus有消息称K Machines计划摧毁整个王国.这些机器最初生活在王国的K个不同城市,从现在起他们可以随时计划并发动攻击.因此他要求Neo摧毁一些道路以破坏机器之间的连接,即在摧毁这些道路之后,任何两台机器之间都不应该有任何路径.

由于攻击可以在任何时间进行,因此Neo必须尽快完成此任务.王国中的每条道路都需要一定的时间才能被摧毁,而且每次只能摧毁一条道路.

您需要编写一个程序,告诉Neo他需要最少的时间来破坏机器之间的连接.

样本输入输入的第一行包含两个空格分隔的整数,N和K.城市编号为0到N-1.然后按照N-1行,每行包含三个以空格分隔的整数xyz,这意味着有一条连接城市x和城市y的双向道路,并且要消耗这条道路需要z个单位的时间.然后按照K行,每行包含一个整数.Ith integer是第i台机器当前所在城市的id.

输出格式在一行中打印中断机器之间连接所需的最短时间.

样本输入

5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0

样本输出

10

说明Neo可以破坏连接城市2和城市4的重量5的道路,以及连接城市0和城市1的重量为5的道路.由于一次只能摧毁一条道路,所以总的最小时间是10个单位时间.在摧毁这些道路后,这些机器都无法通过任何路径到达其他机器.

约束

2 <= N <= 100,000
2 <= K <= N
1 <= time to destroy a road <= 1000,000

有人可以提出如何处理解决方案的想法.

Answer 1

所有三个答案都会得出正确的解决方案，但您无法在 Interviewstreet.com 提供的期限内获得解决方案。你必须想出一些简单的方法来成功解决这个问题。

提示：从机器所在的节点开始。