我本人是二分+点分治+权值线段树做法

分享一下我卡常的经验：

1.对于每颗子树，不要存下所有的路径，而是每种深度只存最大值

2.建出点分树而不是每次二分都重新找重心

3.不要每次二分的时候都重新找路径，把路径存下来。

4.二分check中如果一旦已经出现非负路径，直接一路return让check返回true

5.二分上下界设置为最小/大边权，而不是0/1e6

6.线段树值域的上界设置为min(R,子树最大深度)，而不是R。

7.相信吸氧的vector会跑的飞快的

相信你现在也许不再TLE，而是WA on #4,5，下面是我当时的解决方案：

1.define int LL可让你通过#4。如果你的程序真的因为LL的常数而跌回了TLE的深渊，建议自己手动把一些可能较大的变量开成LL，但我本人开LL以后时间测出来没有任何额外增长。

2.外层套的二分开小，我本人是r-l>=0.00001，大一点都会WA on #5

就这些，祝大家卡常顺利，早日AC

记录：https://www.luogu.com.cn/record/107270645