319. [RQNOJ 184] 洞窟探索

题目背景：

LSZ小朋友组织了一支天文爱好队，他们这次要去探索一个洞窟（天文爱好者怎么探索洞窟？！？），因为据说那里是一个神秘的地方，是地球上最容易捕捉到来自宇宙信息的场所。小朋友带领他的天文爱好队以及许多先进设备来到了洞窟……

题目描述：

洞窟由许许多多的洞穴和通道组成，且任意两个洞穴间有且只有一条路经，每条路经的长度不一定相同。从入口可以进入 1号洞穴，且1号洞穴是唯一与入口相连的洞穴。由于设备有限，小朋友只能在某些洞穴设置他的设备（一个洞穴设一个就足够了）。为了防止迷路，天文爱好队的成员一致决定，每到一个洞窟，就在这里设置一个设备，并留一人看守。

这些设备工作时，任意两个设备间需要通信。通信耗费的时间与这两个洞穴之间的距离有关（指通过通道连接的距离，非两点间距离）。如果有 m个设备，那么共有m*(m-1)/2条路经连接任意两个不同的设备，现在小朋友想知道，选择哪些洞穴，可以使得这些路径的平均长度最小。

平均长度即∑ dist(i,j)/sum,dist(i,j)与dist(j,i)两者只算其中一者（即每两点间的路径长只算一遍）,sum:=m*(m-1)/2。

注意：为了使问题简化，我们假设任何一个洞穴最多与另外三个洞穴直接有通道相连。 1号洞穴最多只与两个洞穴直接有通道相连。

输入：

第一行两个整数 n和m，表示洞穴总数和设备数。

以下 n-1行,每行3个整数x y 和 l，表示一条连接x 和 y 洞穴的通道，长度为l。

输出：

仅一行，一个数：表示最小的平均长度。（保留到小数点后 2位）

输入样例：

4 3

1 2 1

1 3 2

2 4 1

输出样例：

1.33

数据规模：

n<=1500,m<=1000，m<=n

保证每条通道的长度为正，且运算过程中不会有超过 longint的情况（在算法正确时）

样例解释：

选择 1、2、4号洞穴，总路径长1+1+2=4，平均长度：4/3=1.33