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