当线段树打一半发现打错了的时候....想死的心都有了

标程……太麻烦了！
1、对于一棵子树，若这棵子树的根节点上有检查站，则这棵子树就被封锁了，判断是否被封锁可以递归的实现
2、存在一个最优方案，在这个方案中任意一个军队在没有经过根节点的情况下都不会向下移动（远离根的方向）
3、存在一个最优方案，若某军队经过了根，则这军队最终只会到达根的某个儿子，不会再向下走
4、若所有军队只向上移动，一棵子树在某个时刻被封锁后，在以后任意时刻只要这棵子树存在军队，则这棵子树仍被封锁
5、只有空闲的军队才会经过根节点
6、在最终时刻，若根的某个儿子在空闲军队到达时还未被封锁，则最优方案中一定是用空闲军队来封锁这棵子树
所以我们最后有了这样的思路：
首先二分答案，也就是最终时刻T。
接着对于给定的T，计算出每支军队均能想上走多远（以离根的距离为准，若超过根以负数计算）。
然后找出哪些军队是空闲的，根的哪些儿子没有被覆盖。
最后，用离根距离最小（当然有可能为负）的空闲军队去离根最远的儿子上建立检查站，以此类推，若此时仍然有儿子没有被封锁，则最终答案大于T，否则最终答案小于等于T。

COGS的评测姬没Wikioi的快啊……

又是原题额

.

群论都来了

这不是POJ上的么......

真给跪了，o2优化竟然出错。不优化就过了。

不带删除的伸展树……
在splay面前颤抖吧！！！！

我以为O(n2)也可以过的......

最大生成树水过

回复 @cstdio :
神犇不要这样调戏蒟蒻

回复 @Chenyao :
犇！！！！！

非主流方法写的,时间复杂度可以写到O(NS)
(代码写的乱成屎了)

数据有误- -

第3和第10个点答案有问题，应该是无解

回复 @乾坤兑 :
？!

回复 @cstdio :
你不小心打错范围了:它是一个[0,2^23-1]内的整数
应该是32............

最大密度子图，胡波涛论文中的例题(太感动了,60个点,可以手算的小数据多)

标签好吓人。。。