标签： 数学
-
洛谷题库 P1852 跳跳棋 题解与思路重现
我仍然坚持认为这道题不应该放在LCA的专题里面一拿到题我毫无头绪……这看起来跟最近公共祖先没有半毛钱关系啊？我的第一反应是“递推出从某个状态开始能达到的所有状态”，时间复杂度大约是$\mathbf{O}(2^{|N|})$（至于为什么底数为$2$，请看完下一节后思考）。但很明显，坐标在$\pm 10^9$范围内的数据可容不下这般折腾。
但鉴于它被放在这个专题中，我们就尝试从树的角度来考虑。
我仍然坚持认为这道题不应该放在LCA的专题里面
一拿到题我毫无头绪……这看起来跟最近公共祖先没有半毛钱关系啊？我的第一反应是“递推出从某个状态开始能达到的所有状态”，时间复杂度大约是$\mathbf{O}(2^{|N|})$（至于为什么底数为$2$，请看完下一节后思考）。但很明显，坐标在$\pm 10^9$范围内的数据可容不下这般折腾。
但鉴于它被放在这个专题中，我们就尝试从树的角度来考虑。