983E

题目传送门 解题思路：倍增+树剖+树状数组 对于每次询问，我们可以看成是两个点都不断往上跳（如果一个点是另一个点的祖先则是只有一个跳），有一个很明显的贪心策略：每次都跳到能跳到的深度最小的点。然而一次一次往上跳可能被极端数据卡掉，所以要用倍增维护跳 \(2^i\) 次能跳到哪里。 然而两个点都跳到他 ......

分析 很明显，有一个贪心的性质，对于每一次选择路线，一定会选择从当前点能走得最远的一条。 这样就得到了一个暴力做法：预处理好每个点向祖先走得最远的一条路，对于每次询问，两个点暴力上跳，在最近公共祖先处特判一下是否可以一下走完即可。 考虑优化这个过程，找最近公共祖先和上跳都可以倍增处理。唯一的问题是最 ......

水点简单数据结构题！ 考虑从两个点开始往上跳，每次肯定尽可能跳到最浅的点。两个点跳到再跳一步就能到达 lca 的位置的时候，此时再看看有没有路径连接这两个点，如果有那么一步就可以跳到，否则就要跳到 lca 再跳一步，两步跳到。跳的过程显然可以用倍增处理。 然后我们考虑处理出每个点能跳到的最浅的点。假 ......