没看清楚提示，函数调用关系是DAG，不一定是一颗树

回复 @组撒头屯 :
不记得了欸，可能我还没听吧，这题正解反而简单一点，次解更巧妙

回复 @Skylake :
我记得好早之前的集训讲过这题，没记错应该是不停按二进制分两组跑最短路，不过具体分法也忘了

$\mathcal O(Tn\log n\log k)$ 的做法属实人类智慧，感觉比正解还巧妙

回复 @组撒头屯 :
线段树的话好像单次修改的时间复杂度就是 $O(n \log n)$，不太能过的样子
---------------------------------------------------------------------------
好吧，看来是方法不对

数据太弱？我错解（没后面的dp）拿90？

题面有误，出题人谢罪……
另外最后一个点大家注意特判长度为1的线段哦！

回复 @组撒头屯 :
az是我眼瞎了

回复 @Flyhouse :
《长度小于 r 且大于 l》
所有人赛时都这么写的，只有你的标算写的是“长度小于等于 r 且大于等于 l”，考虑赛时无法通知所有人只能改数据，不过现在你修一下题面也行

？？？为甚么改我的数据？？？
洛谷多个标程测试无误

回复 @组撒头屯 : 没看出来这可以直接分块 qwq，用珂朵莉树，每隔一段时间重构一次，时间复杂度不太行（算了下大概是 $\mathcal O(n\sqrt{m}\log{\sqrt{m}})$ 的样子），而且因为我懒，实现得常数很大，如果常数小点或许（？ 不开 O2 也能过
upd：看来是我查询的时候也把块拆开导致了不必要的重构，把查询改成暴力，重构时间拉长点就能过了

回复 @Skylake :
实际上线段树应该也是可行的，但是竟然没人写

@Skylake ，所以你写了个珂朵莉树?!

你最好有逝

大水题！！！！！！！

行内公式：$L=\frac{1}{|G|}\sum_{i=1}^{|G|}D(a_i)$
行间公式：$$L=\frac{1}{|G|}\sum_{i=1}^{|G|}D(a_i)$$

水题

分块大法好啊！

调了整整一晚上，属实给我整不会了

回复 @夜莺 :
NB