Description:


Input:


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

Output:


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

Sample Input:


Sample Output:


题解:


这一道题自从2016.9.27加了一组数据之后,我在网上没有找到一个可以过的标程。
真的还是改了很久的,靠普通的方法会TLE,因为会被卡成 \(O(n^2log_2^2 n)\)
好吧进入正文:

这个题目要求树上路径长度在[L, U]之间的路径的权值平均值的最大值。

当涉及到路径上权值的平均值的时候,一般就会用到01分数规划,即二分平均值,每一条边都减去二分的值,然后判断该路径权值和是否大于或等于零。之前我一直不知道这个叫做01分数规划。

然后我们考虑点分治,找到树的重心,分路径经过重心和不经过两种情况。不经过递归处理子树,经过的话使用单调队列优化DP。
具体地说,设f[x]表示以重心为起点,长度为x的路径的最大权值。我们依次对于重心的每一棵子树进行BFS,得到的BFS的队列中的点即是按照深度排序的。那么我们再遍历该队列,对于点i,f上区间在[L-i, R-i]的值可以更新答案,然后用一个单调队列维护DP,就可以了。
话说我之前一直不知道单调队列是什么。

完成以上步骤后你就可以完美地TLE了(╯‵□′)╯︵┴─┴

作为TLE了5个小时的我看遍各个网上的代码仍找不到错误。。。一怒之下交了标程,发现标程TLE了(╯‵□′)╯︵┴─┴
我能怎么办?我也很无奈啊 ◢▆▅▄▃崩╰(〒皿〒)╯潰▃▄▅

感谢西藏凯的帮助,让我在人生低谷找到了信心,这一组2016.9.27加入的数据大有来头。。。

西藏凯给出了一种情况,如果对于一个点,它的一个子树是一条链,另外的子树都是一个点,这个算法就会被卡成 \(O(n^2log_2^2 n)\)
于是我们在二分前把每一个子树按照点数排序,就可以避免这个问题(应该是对的)
然后就可以AC了,这个AC来之不易啊~~~

TLE代码如下:

AC代码: