2020-2021:teams:hotpot:lca

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:hotpot:lca [2020/07/16 14:39]
misakatao 更新
+++ 2020-2021:teams:hotpot:lca [2020/07/22 13:39] (当前版本)
misakatao 更新
@@ 行 9: / 行 9: @@
 令$f[i][j]$表示点$i$的第$2^j$个祖先是谁，显然$f[i][0]$就是$i$的父亲，而这个信息我们可以递推，显然$f[i][j] = f[f[i][j-1]][j-1]$，即我的第$2^{j-1}$个祖先的第$2^{j-1}$个祖先是我的第$2^j$个祖先，所以我们只要知道了所有的$f[i][0]$，就可以推出所有的信息。
-在实际求两个点的LCA时，我们依照刚刚的想法，先把深度更深的点向上跳到和深度浅的点同深度，这一过程可以依据$f$数组在$O(\log n)$的时间内完成，然后两个点一起往上跳，时间也是$O(\log n)$。具体代码如下
+在实际求两个点的LCA时，我们依照刚刚的想法，先把深度更深的点向上跳到和深度浅的点同深度，这一过程可以依据$f$数组在$O(\log n)$的时间内完成，然后两个点一起往上跳，时间也是$O(\log n)$。正是因为这一算法的信息是以2的幂次为基础，所以被称为倍增算法。具体代码如下
 <code cpp>
@@ 行 42: / 行 42: @@
 ======Tarjan算法求LCA======
+除了倍增算法，Tarjan爷爷发明的Tarjan算法也可以用来求LCA。
+首先我们需要记录下所有的查询，因为用Tarjan求LCA必须要离线才能做，如果形式是在线就无法使用Tarjan。
+接下来我们要从根开始遍历所有的点，当一个点的子树被遍历完以后，把它的所有儿子在并查集中与它合并并回溯到它的父亲。当我们遍历到一个点的时候，我们依次查看所有与这个点相关的查询，若另一个点已经被遍历过，那么它在并查集中的父亲就是这一组询问的LCA。这一算法的原理是，我们遍历到一个点时，设这个点是$x$，若我们查询了$(x,y)$且$y$已经被遍历，那么$y$一定已经向上合并了，设$LCA(x,y)=z$，那么由于我们刚刚遍历到$x$，说明$z$肯定还没有被向上合并，而$y$一定已经合并到了$z$，否则说明$x$和$y$在$z$的同一个子树里，那么$z$显然不是$x$和$y$的LCA。
+更具体的讲解和代码可以看[[https://www.cnblogs.com/abc2237512422/p/9832468.html|这篇博客]]，其中最后还有一个可以手动控制的算法流程详解，可以帮助理解。
 ======树链剖分求LCA======
-======RMQ算法求LCA======
+[[treechain|树链剖分]]
-======例题——BZOJ1001狼抓兔子======
+======RMQ算法求LCA======
-=====题目大意=====
+RMQ算法本来是在一维数组上求最大最小值的算法，方法与倍增基本一致，令$f[i][j]$表示从$i$向右长度为$2^j$的位置内的最大/最小值，递推方式也与倍增算法一直。
-=====解题思路=====
+那么如何利用RMQ算法求解LCA呢，我们对要求的树首先进行dfs，然后得到每一个点的dfs序，之后我们每次经过这个点，就把这个点放入一个序列的最后，这个序列被称为欧拉序，然后在查询$LCA(x,y)$时，我们首先找到$x$和$y$的dfs序，找到两个dfs序最先出现的位置，那么在欧拉序这两个位置之间dfs序最小的点就是它们的LCA。这一做法还可以进一步优化使得代码难度降低。
-=====代码实现=====

2020-2021/teams/hotpot/lca.1594881580.txt.gz · 最后更改: 2020/07/16 14:39 由 misakatao