983
CF983E
题目传送门 解题思路:倍增+树剖+树状数组 对于每次询问,我们可以看成是两个点都不断往上跳(如果一个点是另一个点的祖先则是只有一个跳),有一个很明显的贪心策略:每次都跳到能跳到的深度最小的点。然而一次一次往上跳可能被极端数据卡掉,所以要用倍增维护跳 \(2^i\) 次能跳到哪里。 然而两个点都跳到他 ......
CF983E
分析 很明显,有一个贪心的性质,对于每一次选择路线,一定会选择从当前点能走得最远的一条。 这样就得到了一个暴力做法:预处理好每个点向祖先走得最远的一条路,对于每次询问,两个点暴力上跳,在最近公共祖先处特判一下是否可以一下走完即可。 考虑优化这个过程,找最近公共祖先和上跳都可以倍增处理。唯一的问题是最 ......