Level Ancestor 问题

接口与参数约定 ​

根的深度固定为 $0$。对节点 $v$ 和目标深度 $d$，定义

$$LA(v,d)=v\text{ 在深度 }d\text{ 的唯一祖先},0\le d\le depth(v).$$

等价的第 $k$ 个祖先接口返回 $LA(v,depth(v)-k)$，其中 $0\le k\le depth(v)$；$k=0$ 返回 $v$，$k=depth(v)$ 返回根。页面以下用目标深度 $d$，避免把“深度”与“向上步数”混作同一参数。

树的唯一根路径保证答案存在且唯一。若 $d>depth(v)$ 或 $d<0$，接口应返回 $\mathrm{\perp }$ 或拒绝查询，不能依赖数组越界偶然充当哨兵。

Binary Lifting 基线 ​

二进制倍增公理库二进制倍增Binary lifting · Doubling technique预计算函数的 $2^k$ 次迭代，用输入步数的二进制展开快速跳转。保存

$$up[j][v]=v\text{ 的第 }{2}^j\text{ 个祖先}.$$

预处理与空间为 $O(n\log n)$，查询把 $k=depth(v)-d$ 按二进制分解，用最坏 $O(\log n)$ 次跳转到答案。这一路线简单，还能同步维护路径摘要，但不是静态 Level Ancestor 的最优空间—查询组合。

线性空间常数查询的结构图像 ​

静态树可用 longest-path/ladder decomposition 把节点划进若干从祖先到后代的 ladder，并把每条 ladder 向上复制至多自身长度。所有原 ladder 总长为 $n$，扩展后的总表长仍为 $O(n)$。

查询先令 $k=depth(v)-d$，用最高置位选择一个覆盖至少 $2^{\lfloor \log k\rfloor }$ 级祖先的预计算跳转，再在包含目标祖先的扩展 ladder 中按深度差直接索引。Long-path 选择保证跳转后的剩余距离落在该 ladder 已复制的祖先前缀内。

配合常数时间最高置位/微表，Bender–Farach-Colton 型方案可在 Word-RAM 上取得

$$O(n)\text{预处理},O(n)\text{空间},O(1)\text{最坏查询}.$$

结论针对静态根树，且常数查询依赖 $w=\mathrm{\Omega }(\log n)$ 的寻址与字级选择；不能只写“用 ladder”便省略模型。

可追踪真例 ​

设根路径为 $r-a-b-c-d$，另有分支 $b-x-y$。深度依次为 $0,1,2,3,4$，且 $depth(x)=3,depth(y)=4$。

$$LA(y,1)=a,LA(y,2)=b,LA(d,3)=c.$$

第 $3$ 个祖先查询 ancestor(y,3) 与 $LA(y,1)$ 是同一答案；若把参数 $3$ 错当成目标深度，就会返回 $x$，这正是两种 API 混用的典型错误。

与 LCA、动态树的区分 ​

最近公共祖先公理库最近公共祖先Lowest common ancestor · LCA根树中同时为两个节点祖先且深度最大的节点及其查询问题。输入两个节点并寻找最深公共祖先；Level Ancestor 输入一个节点和一个深度。LCA 算法可以调用祖先跳跃作为子程序，Level Ancestor 也能帮助对齐深度，但两个问题的接口和最优预处理并不相同。

若树发生 link、cut 或换根，深度和 ladder 可能整体改变，静态线性预处理立即失效。动态版本应进入动态森林问题公理库动态森林问题Dynamic forest problem维护无环树族的 link、cut、连通、换根及路径或子树聚合接口。并分别报告更新、查询及换根成本，不能沿用本页 $O(1)$ 查询而不计维护。

简洁树表示还可用平衡括号与 rank/select 支持祖先导航；其重点是 bit 空间，而非把指针树的 $O(n)$ words 与 $2n+o(n)$ bits 写成同一空间界。

参考资料

• Michael A. Bender and Martín Farach-Colton, “The Level Ancestor Problem Simplified,” Theoretical Computer Science 321(1), 2004.
• Omer Berkman and Uzi Vishkin, “Finding Level-Ancestors in Trees,” Journal of Computer and System Sciences 48(2), 1994.
• Paul F. Dietz, “Finding Level-Ancestors in Dynamic Trees,” WADS, 1991, for the dynamic contrast.