问题定义 .#

最近公共祖先简称。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。
为了方便，我们记某点集  的最近公共祖先为  或 。

. 解法 .#

 前置知识 #

欧拉序#

在树上做一次深度优先遍历(DFS)，每当到达一个节点(无论是首次进入,还是处理完所有子节点后回溯回来)，就把该节点记录下来，由此得到的节点序列称为欧拉序(Euler tour)。
一种较为形式化描述是：
从根节点 root 开始执行以下递归过程：

是

否

开始: dfs u

记录节点 u 到欧拉序

还有未处理的子节点?

取下一个子节点 v

递归调用 dfs v

记录节点 u 到欧拉序

结束

RMQ#

RMQ 问题指区间最值查询（Range Minimum/Maximum Query）。

 欧拉序与RMQ问题 #

好了，了解完前面的知识，我们就要引出一个重要性质：

性质1#

记  为节点 u 第一次在欧拉序中出现的位置。
对于任意两个节点 u,v，设 ,
则:

即区间 [l,r] 中深度最小的节点就是 u 与 v 的最近公共祖先。

#

设 。节点  和  分别位于  的不同子树中，或者其中一个就是  本身。
考察从首次进入  到首次进入  这段欧拉序对应的遍历过程：当 DFS 首次到达 （位置 ）后，算法会回溯到 ，再向下进入 （到达位置 ）。因此  必然在区间  内至少出现一次。
对于该区间内的任意一个节点 ，它出现在  到  之间，意味着在从  回溯到  并前往  的过程中访问了 。由 DFS 的性质，这期间访问的所有节点都位于  的子树中（包括  本身）。故有：

当且仅当  时等号成立。因此，区间  内深度最小的节点恰好就是 ，即：

证毕。

 RMQ求法 #

你该不会认为这章最简单吧
你该不会直接套ST表吧，很显然，还是太不优秀了
当然不会直接套 ST 表。注意到我们的欧拉序有一个极其特殊的性质：相邻两个元素的深度差恰好为 。这引出了解决一般 RMQ 问题最优秀的算法之一—— RMQ，它可以将预处理复杂度压到真正的 ，同时保持  查询。

 RMQ 算法#

我们面对的序列 （此处 ，即欧拉序长度）满足：

我们要在线回答  的位置。
算法的核心思想是分块 + 状态压缩
第一步：分块与块间稀疏表
令块大小 （在  时 ）。将序列划分为  个块。
对块的最小值建立稀疏表（Sparse Table）。具体地，令 第块中的值，在数组  上运行标准 ST 表预处理。这一步时空复杂度均为 ，由于 ，这其实是  的。
第二步：块内本质类的数量
对于块内查询，若对整个数组的每一块都暴力跑 ST 表或全预处，空间会爆炸。但注意到  性质把块内的“形状”限制在极小的范围内。
考虑任意一个长度为  的块，对其内部元素作差分：

因此，给定该块的首元素值，整个块由这个长度为  的  差分序列唯一决定其相对形态。差分序列总共只有  种。由 ，得种类数约为：

这是一个远远小于  的数量级（ 时约  多种）。
第三步：块内查询的预打表
对于这至多  种差分类型，我们完全可以预处理出每一种类型在任意区间 （）内的最小值位置。
第四步：回答查询
对于一个查询 ：

• 若  在同一块内，直接用块内预打表结果，。
• 若跨块，则区间被分为：左端块的后缀 + 中间若干整块 + 右端块的前缀。
  • 左端块后缀、右端块前缀：分别用块内预打表  得到最小值位置。
  • 中间整块：在第一步的块稀疏表上做一次  RMQ。
  • 在得到的至多三个候选位置中，比较它们在原序列  中的深度，选取最小的那个。。

. 时间复杂度分析 .#

 符号约定与基础规模#

设树有  个节点。进行一次深度优先遍历（DFS）得到欧拉序，欧拉序的长度  具有如下性质：

性质2（欧拉序长度）
对于 ，欧拉序的长度 。
证明. 在DFS过程中，每个非根节点被记录两次：一次进入，一次回溯至父节点；根节点被记录一次进入，且最后一次回溯不产生新的记录。总计记录次数为 。
故 ，在后继复杂度分析中可直接视  与  同阶。

我们的目标是在序列 （此处 ）上支持区间最小值位置查询，并且序列满足  性质：

 分块与块间稀疏表#

令块大小 。将  划分为  个块，记第  个块的最小值（按深度）为 。

对数组  建立稀疏表（Sparse Table），以支持在  时