求LCA方法总结前言求LCA是十分基础的东西，但是方法众多。此篇介绍OI中常用的求法。倍增求LCA蒟蒻最先学的求LCA方法就是倍增求LCA。预处理和查询时间复杂度均为单\(\log\)。优点为好理解，比较简单，且便于处理路径数据。树剖LCA重链剖分。优点是预处理是线性复杂度，

DFS序求LCA介绍欧拉序求LCA的数组总是会忘记开两倍，并且预处理的常数较大。用DFS序求LCA可以解决这些问题。欧拉序：进节点和出节点会重复记录节点。DFS序：深度优先搜索的顺序，不会重新记录。假设要求\(lca(u,v)\),且\(dfn[u]<dfn[v]\)。那么\(dfn[u]\simdfn[v]\)的

前言想象我在口胡三样我都不熟悉的东西并尝试称之为“学习笔记”。其实不过是我自己对于它的一点小理解，甚至可能是错误的！无所谓，口胡！口胡！口胡！口胡！口胡！一些备注\(dfn_u\)为点\(u\)的dfn序，\(nfd_i\)表示第\(i\)个dfs到的点是啥（前者的反数组）dfs序求lca这个很简单，想

前言为什么用dfs序求LCA而不用欧拉序？帅常数小，也就一半好玩反正没什么正经理由。正文定义dfs序是指对树进行深度优先遍历后得到的节点序列。\(\mathit{dfn}_i\)是节点\(i\)在dfs序中的位置（从\(0\)或\(1\)开始无影响）。LCA是最近公共祖先。深度\(\ma

前言为什么用dfs序求LCA而不用欧拉序？帅常数小，也就一半好玩反正没什么正经理由。正文定义dfs序是指对树进行深度优先遍历后得到的节点序列。\(\mathit{dfn}_i\)是节点\(i\)在dfs序中的位置（从\(0\)或\(1\)开始无影响）。LCA是最近公共祖先。深度\(\ma

最近学了一点黑科技，这就是一个。有一个结论比如这就是一个dfn序。在代码中，常常对beg和ed都开一个数组。如果一个点是x,y的lca记为g，那么有以下结论\(beg[g]<min(beg[x],beg[y]),ed[g]>max(ed[x],ed[y])\)感性理解即可。所以我们就可以在符合的点找深度最大的。这是一种思路，常常

使用欧拉序st表O(1)求LCA 欧拉序 st 表求LCA一开始是从某篇题解里看到的，后来百度了一下就会了（这是一种预处理 O(nlogn) ，查询 O(1) 的优秀算法。什么是欧拉序举个例子，下面是一棵树：上面有 dfs 与回溯的过程。将整个 dfs 与回溯过程写出来：1  →  2

前置知识DFN序：对一棵树进行深度优先搜索DFS得到的结点序列，即深度优先搜索DFS的访问顺序。该表述不一定严谨，建议百度ST表（SparseTable，稀疏表）算法概述引理1.1在DFN序中祖先一定出现后代之前。考虑一树上的两个节点\(x\)，\(y\)的最近公共祖先\(d\)，设\(x\)的DFN序

Updateon2023.7.17：该技巧目前已知的最早来源：skip2004。Updateon2023.7.17：比较时，取时间戳较小的结点也是正确的，不用记录深度。DFS序求LCA无论是从时间常数，空间常数还是好写程度方面均吊打欧拉序。定义DFS序表示对一棵树进行深度优先搜索得到的结点序列，而时间戳DFN