Link-cut Tree 加上Special Read可以达到这个速度：

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 462ms

├ 测试数据 05：答案正确... 431ms

├ 测试数据 06：答案正确... 431ms

├ 测试数据 07：答案正确... 462ms

├ 测试数据 08：答案正确... 1150ms

├ 测试数据 09：答案正确... 1134ms

├ 测试数据 10：答案正确... 1181ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：5251ms

在我的电脑上加O2能到0.7s……

裸的树链剖分，懒得写了。

占位..这题编程难度有点大啊..

树链剖分吧..

询问a b等价于询问max(a-lca这一段中的最大值，以及包含lca的最大值，以及b到lca这一段中的最大值）

看这个题目,差点把小白的交了

getchar是比较牛叉的：

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 212ms

├ 测试数据 05：答案正确... 306ms

├ 测试数据 06：答案正确... 244ms

├ 测试数据 07：答案正确... 228ms

├ 测试数据 08：答案正确... 806ms

├ 测试数据 09：答案正确... 728ms

├ 测试数据 10：答案正确... 697ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3221ms

Orz oimaster

这题很难啊

MS程序很大的

我再好好学学在做