2020-2021:teams:hotpot:lca
这是本文档旧的修订版！
问题概述
LCA的全称是Least Common Ancestors，顾名思义，LCA问题就是求树上两个点的最近公共祖先的问题。由定义，两个点的最近公共祖先是满足这两个点都在其子树中的点里面深度最大的那个，因此有可能这两个点的最近公共祖先就是其中一个。
倍增算法求LCA
Tarjan算法求LCA
树链剖分求LCA
RMQ算法求LCA
例题——BZOJ1001狼抓兔子
题目大意
解题思路
代码实现
2020-2021/teams/hotpot/lca.1594880722.txt.gz · 最后更改: 2020/07/16 14:25 由 misakatao
