P3984 - [WC2010]重建计划

题目

P3984[WC2010]重建计划

限制 : 时间限制 : - MS 空间限制 : 165536 KB

评测说明 : 4s

第一行包含一个正整数N，表示X国的城市个数.
第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限
接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号

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

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

2.500

12
3 5
1 2 804224
1 3 645617
2 4 763931
2 6 744133
2 8 534824
4 5 163318
6 7 421158
6 10 773167
6 11 380598
8 9 639836
9 12 261707

773841.333

20%的数据,N<=5000
30%的数据,N<=100000,原有方案恰好为一条路径
100%的数据,N<=100000,1<=L<=U<=N-1,Vi<=1000000

update 2022.03.04：nodgd添加2组数据并重测，大量小伙伴惨遭TLE。