我们就让每个军队在二分的时间内尽量向上跳,看能不能在给定的时间内跳到节点 111
如果能,就先让这个军队跳上去,记录下这个军队到节点 111 时的剩余时间 RestRestRest 和它在向上跳的路径中 111 的儿子 TopTopTop ,便于 后来的处理。
如果不能,就让这个军队尽量往上跳,并在终点打上控制标记(毕竟越往上跳控制的节点肯定不会比在原来的点少)
处理完所有的军队后,我们再将所有能蹦到节点 111 的军队按照 RestRestRest 进行从小到大的排序
然后如果这个点的 RestRestRest 已经不能再从 111 蹦回 TopTopTop 了并且 TopTopTop 还没有被控制,那就让这个点别在节点 111 呆着了,直接回到 TopTopTop 顺便把 TopTopTop 节点控制了就行啦,因为如果它不回去,肯定还要有别的地方的军队来控制 TopTopTop ,那样显然距离更远。
最后再把所有没有被控制的节点 111 的儿子(注意: 如果这个点的所有子树的叶子节点被控制了,那这个点也算是被控制了)加入队列,然后再按从大到小排个序。
最后把现在仍在节点 111 的军队按照 RestRestRest 从大到小排个序,然后和没被控制的节点一一比对就好辣
具体做法说完了,然后我们观察数据范围, nnn , m<=50000m<=50000m<=50000 ,暴力向上跳肯定是会 TTT 的
所以我们使用倍增进行优化
fff [ iii ][ jjj ]表示从 iii 这个点跳 222 ^ jjj 步能跳到的节点
ststst [ iii ][ jjj ]表示从 iii 这个点跳 222 ^ jjj 步的距离
然后军队向上提的时候就和倍增求 LCALCALCA 类似,这样一来就可以 AAA 掉此题