LCA（最近公共祖先）

洛谷题库 P1852 跳跳棋

我仍然坚持认为这道题不应该放在LCA的专题里面

一拿到题我毫无头绪……这看起来跟最近公共祖先没有半毛钱关系啊？我的第一反应是“递推出从某个状态开始能达到的所有状态”，时间复杂度大约是$\mathbf{O}(2^{|N|})$（至于为什么底数为$2$，请看完下一节后思考）。但很明显，坐标在$\pm 10^9$范围内的数据可容不下这般折腾。

但鉴于它被放在这个专题中，我们就尝试从树的角度来考虑。

（更多…）