标签: 树剖

1 篇文章

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