#1758. [Wc2010] 重建计划

[Wc2010] 重建计划

题目描述

XX 国遭受了地震的重创,导致全国的交通近乎瘫疾,重建家园的计划迫在眉睫。

XX 国由 NN 个城市组成,重建小组提出,仅需建立 N1N-1 条道路即可使得任意两个城市互相可达。于是,重建小组很快提出了一个包含 N1N-1 条道路的方案,并满足城市之间两两可达,他们还计算评估了每条道路 ee 建设之后可以带来的价值 v(e)v(e)

由于重建计划复杂而艰难,经费也有一定限制。因此,政府要求第一期重建工程修建的道路数目为 kk 条,但需满足 LkUL\leq k\leq U,即不应少于 LL 条,但不超过 UU 条。同时,为了最大化利用率,要求建设的这些道路恰好组成一条简单路径,即所建设的 kk 条路径可以构成一个排列 e1=(p1,q1),e2=(p2,q2),,ek=(pk,qk)e_1=(p_1,q_1), e_2=(p_2,q_2),\cdots ,e_k=(p_k,q_k),对于 1i<k1\leq i<k,有 (qi=pi+1)(q_i=p_{i+1})

重建小组打算修改他们的原有方案以满足要求,即在原有的 N1N-1 条道路中寻找一条路径 SS 作为新的方案,使得新方案中的道路平均价值

$$\text{AvgValue}=\dfrac{\displaystyle\sum_{e\in S}v(e)}{|S|} $$

最大。这里 v(e)v(e) 表示道路 ee 的价值,S|S| 表示 新方案中道路的条数。请你帮助重建小组寻找一个最优方案。

注:在本题中 LLUU 的设置将保证有解。

输入格式

第一行包含一个正整数 NN,表示 XX 国的城市个数。

第二行包含两个正整数 LLUU,表示政策要求的第一期重建方案中修建道路数的上下限。

接下来的 N1N-1 行描述重建小组的原有方案,每行三个正整数 Ai,Bi,ViA_i,B_i,V_i分别表示道路 (Ai,Bi)(A_i,B_i),其价值为 ViV_i,其中城市由 1N1\sim N 进行标号。

输出格式

输出最大平均估值,保留三位小数。

样例

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

数据规模与约定

对于 100%100\% 的数据:N105N\leq 10^51LUN11\leq L\leq U\leq N-1Vi106V_i\leq 10^6

题目来源

WC2010