我怎么就没有想到用树状数组，而去线段树TTT了呢。。。。药丸

样例好评

我表示不能理解，明明树剖用堆线段树维护(id=299174)是O(nlon^3)而整体二分(id=376787)是O(nlogn^2)的，为什么反而整体二分慢？

回复 @riteme :
虽说ST可以做到O(nlongn)预处理，O(1)查lca，但是你整体二分肯定要配合树状数组或者线段树之类的吧，那样整体二分的复杂度就是O(nlongn^2)了，你的整体复杂度还是O(nlongn^2)的，而且你用的是树剖求lca，每次是O(logn)的，不过因为是离线，所以求出所有lca的复杂度还是O(nlongn)的。
这道题应该没有时间渐进复杂度低于O(nlongn^2)的做法了，（还是我太弱不会？）如果有，还请大神讲解。

回复 @riteme :
感谢神犇的知道，NOIP后我才知道树上的链修改点求值可以变成点修改子树求和。

回复 @Mike is Fool :
使用线段树分治 + $O(1)$的LCA查询可以做到二分过程$O(n \log n)$

有人用整体二分写吗，整体二分带树剖好像是O(nlog^3n)，显然会挂。总不是要带LCT吧

%%%

用堆来维护线段树，再用这棵线段树来维护树剖，这考试时就算想到也不敢写啊！

树剖加堆，送分题啊，考场上没写出来