<a href="https://en.wikipedia.org/wiki/Levelancestorproblem">层级祖先问题的核心在于，如何对一棵给定的有根树 $T$ 进行预处理，构建一种数据结构，使其能够快速确定树中某个节点在特定深度（距离根节点的特定距离）上的祖先节点。在这里，树中任意节点的“深度（depth）”指的是从树的根节点到该节点的最短路径上的边数。
给定的树被表示为一个具有 $n$ 个节点和 $n-1$ 条边的 无向连通图。
解决上述查询问题的思路是使用 跳指针算法。该算法可以在 $O(n \log n)$ 的时间内对树进行预处理，并在 $O(\log n)$ 的时间内回答层级祖先查询。在跳指针算法中，对于每个节点 $N$，我们都建立指向其第 $j$ 代祖先的指针，其中 $j$ 取值为 1, 2, 4, 8, … 等等。我们将这些指针称为 JumpN[i]，其中
$\text{Jump}_u[i] = \text{LA}(N, \text{depth}(N) – 2^i)$。
当算法需要处理一个查询时，我们利用这些跳指针在树中反复向上跳跃。由于跳跃的次数最多为 $\log n$，因此查询可以在 $O(\log n)$ 的时间复杂度内完成。
为此，我们需要存储每个节点的 第 $2^i$ 代祖先，并计算每个节点相对于树根的深度。
现在，我们的任务简化为寻找节点 $N$ 的第 $(\text{depth}(N) – 2^i)$ 代祖先。让我们将 $X$ 记作 $(\text{depth}(N) – 2^i)$，并假设 $X$ 的二进制表示中有 $b$ 个置位（bit 为 1），分别记为 $s1, s2, s3, \dots, sb$。
$X = 2^{(s1)} + 2^{(s2)} + \dots + 2^{(s_b)}$
那么，我们该如何找到每个节点的 $2^j$ 代祖先以及它们距离根节点的深度呢？
首先，我们要知道每个节点的第 $2^0$ 代祖先（即父节点）。我们可以递归地计算出第 $2^j$ 代祖先。我们知道，第 $2^j$ 代祖先就是第 $2^{j-1}$ 代祖先的第 $2^{j-1}$ 代祖先。为了计算每个节点的深度，我们使用祖先矩阵。如果我们在第 $k$ 个元素的第 $j$ 个索引处的数组中找到了根节点，那么该节点的深度就是 $2^j$；但是，如果第 $k$ 个元素的祖先数组中没有出现根节点，那么第 $k$ 个元素的深度计算公式为：$2 \times (\text{第 } k \text{ 行最后一个非零祖先的索引}) + \text{第 } k \text{ 行最后索引处祖先的深度}$。
下面是使用动态规划填充祖先矩阵和计算每个节点深度的算法。在这里，我们将根节点记作 R，并最初假设根节点的祖先是 0。同时，我们将深度数组初始化为 -1，表示当前节点的深度尚未设置，我们需要计算它。如果当前节点的深度不等于 -1，则意味着我们已经计算过了它的深度。
// 我们知道每个节点的第一个祖先，所以 j >= 1
For j >= 1
ancstr[k][j] = k 的第 2^j 代祖先
= (k 的第 2^{j-1} 代祖先) 的第 2^{j-1} 代祖先
= ancstr[ancstr[i][j-1][j-1]
if ancstr[k][j] == R && depth[k] == -1
depth[k] = 2^j
else if ancstr[k][j] == -1 && depth[k] == -1
depth[k] = 2^(j-1) + depth[ ancstr[k][j-1] ]
让我们通过下面的图解来理解这个算法。
在给定的图中，我们需要计算值为 8 的节点的第 1 层祖先（深度为 1 的祖先）。首先，我们要建立祖先矩阵，用于存储节点的第 $2^i$ 代祖先。现在，节点 8 的第 $2^0$ 代祖先是 10，同理节点 10 的第 $2^0$ 代祖先是 9，节点 9 的是 1，节点 1 的是 5。基于上述算法，节点 8 的第 1 层祖先是节点 8 的第$(\text{depth}(8)-1)$ 代祖先。
我们要预先计算每个节点的深度，已知节点 8 的深度为 5，所以我们最终需要找到节点 8 的第 $(5-1) = 4$ 代 祖先，这等价于 [节点 8 的第 $2^1$ 代祖先] 的第 $2^1$ 代祖先。而 节点 8 的第 $2^1$ 代祖先 是 [节点 8 的第 $2^0$ 代祖先] 的第 $2^0$ 代祖先。因此，[节点 8 的第 $2^0$ 代祖先] 的第 $2^0$ 代祖先 是值为 9 的节点，而节点 9 的 第 $2^1$ 代祖先 是值为 5 的节点。通过这种方式，我们就可以在 $O(\log n)$ 的时间复杂度内计算所有查询。
实现：
C++
`
// CPP program to implement Level Ancestor Algorithm
#include
using namespace std;
int R = 0;
// n -> it represent total number of nodes
// len -> it is the maximum length of array to hold
// ancestor of each node. In worst case,
// the highest value of ancestor a node can have is n-1.
// 2 ^ len <= n-1
// len = O(log2n)
int getLen(int n)
{
return (int)(log(n) / log(2)) + 1;
}
// ancstr represents 2D matrix to hold ancestor of node.
// Here we pass reference of 2D matrix so that the change
// made occur directly to the original matrix
// depth[] stores depth of each node
// len is same as defined above
// n is total nodes in graph
// R represent root