最近公共祖先(LCA) 2021-12-15 13:25 | 1,985 | 0 | OI,算法 1398 字 | 12 分钟 代码针对洛谷P3379 1.向上标记法 最朴素的求最近公共祖先的方法,两个子结点同时向上一个一个的跳,标记已经跳过的点,如果有一个点跳到了已经标记过的点,那么就说明这个点就是最近公共祖先。可以自己简单的推一下,查询的时间复杂度为 $ O(n) $ 。 2.倍增 总思路:用类似于二进制拆分的思想。 首… LCA倍增树剖