GMQ出品，$LCA$ 算法总结

目录

• 一、前言
• 二、$LCA$ 问题概述
  • （一）什么是 $LCA$ 问题？
  • （二） $LCA$ 问题的主要应用
  • （三）常用求 $LCA$ 算法
• 三、求 $LCA$ 的算法详解
  • （一）在线LCA的算法（爬树法）

一、前言

这是 $LCA$，可不是 liu_cheng_ao ，也不是 印度某不靠谱工程 哟

二、$LCA$ 问题概述

（一）什么是 $LCA$ 问题？

$LCA$：$Lowest Common Ancestor$基于有根树最近公共祖先问题。

$LCA(T,u,v)$：给定一棵有根树 $T$ 和两个结点 $u$ 和 $v$，找到距离 $u$ 和 $v$ 的最近的共同祖先结点，称为 $LCA$ 问题。

比如这张图：

对于该有根树 $T$，满足$\begin{cases}LCA(T,5,2)=1\\LCA(T,3,4)=3\\LCA(T,4,5)=3\end{cases}$

（二） $LCA$ 问题的主要应用

$LCA$ 用于求解两个点在这棵树上距离最近的公共祖先节点。

所以 $LCA$ 主要是用来求解${\color{Red}当两个点仅有唯一一条确定的最短路径时的路径}$这一类问题。

（三）常用求 $LCA$ 算法

• 【在线 $LCA$ 算法】：类 $ST$ 算法，又称爬树法
• 【离线 $LCA$ 算法】： $Tarjan$ 算法
• 【$LCA$ 向 $RMQ$ 的转化】：利用 $DFS$ 将 $LCA$ 转化为 $RMQ$ 问题

未完待续~~QAQ