。

用两个堆将覆盖自己子树与覆盖别的子树的情况分开枚举是80分
排完序不分情况枚举AC
我也很绝望啊qwq

貌似很少人用树剖

细节的处理是食人的妖魔

不加点注释不舒服

终于a了qwq
之前有一个特别大的错误
竟然还过了9个点

回复 @mikumikumi :
总算知道为什么WA了。。。

回复 @紅蓮之心熾熱��_血瞳洞穿無盡陰暗 :
为啥我用倍增，开O2，写register都f**k不过去呢？

这题让我心碎

又用倍增写了一遍，果然最后一个点不T了。

论和别人写法不一样的后果：
你有的情况不会处理，别人都不能教你！

%%%

按照这题给的数据范围是可以造出答案爆int的数据的，所以我一开始把二分答案的上界设成了1LL<<62.但是其实1LL<<20就能在这儿AC，完全不用longlong...

%%%

回复 @mikumikumi :
( 排序之后从小的跑一遍优先解决自己子树的就是最优的了
吐槽: 半个下午.... 把5e4看成了5e5...... M了两次

一个细节：
从x子树走到首都的军队，并不一定要它去封锁x所在的子树，用从y号子树走到首都的军队去封锁x，有可能会更优。

还是贴一下90分的代码……这个没有考虑“第二阶段中进驻到首都的军队比最初部署到首都的军队更‘无用’”的情况……（太拗口……）
@chs

回复 @Asm.Def :
那BST，还(tu)有(hao)为(wo)什(men)么(zuo)打(peng)$(you)$(ba)。。。。

回复 @天一阁 :
我能说我没看懂吗QAQ

刚开始忘写注释了= =加上注释再提交一遍= =
思想是二分加贪心判断，中间用到了好多排序以及BST（直接套的STL - multiset实现的），总时间复杂度为$O(n \lg^2 n)$