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

可耻地直接复制粘贴了以前火柴排队的代码改了下。。。咦？这个模数。。wc2016 wifi密码啊

回复 @姬树流 :
四高一

1.没有绅士来出一个强制在线的盗版题么...要不然对于明明理论效率一样却被卡常数的树套树实在不公平啊
2.两个优化细节：sort改成与cdq同步的归并排序。拆成4个的查询可以拆成2个。

pbds大法好

有无数个潜在bug的ac代码，数据太弱，╮(╯_╰)╭，交错代码调了十年

跑得慢的优化还是naïve啊，要加上舍伍德算法，当然拉斯维加斯可能会更快，不过楼上的开栈代码真厉害

Orz..dalao们的树套主席树写的太神辣！那个开栈代码太秒辣！

喵喵喵~

精心伪装的暴力……

tarjan求割点，从1开始，要求子树中存在点N才算是合格的割点

原来Unsigned BigDouble这么快,可能我FTNT递归炸了,
orz楼上的开栈代码

f[i][j]表示前i分钟在疲劳度为j的情况下所能走的最远distance
f[i][0]=max(f[i-1][0],f[i-j][j]) i-j>=0;
f[i][j]=max(f[i][j],f[i-1][j-1]+d[i]);
~

恶心这道题

忘初始化...
身败名裂...

已改

数据范围呢

%%%

莫队大法好，暴力出奇迹
终于学会莫队了= =