最近公共祖先 (lowest common ancestor) 是一个有根树中，两个节点深度最大的共同祖先。其详细性质可见 最近公共祖先。求解最近公共祖先有多种算法。

朴素算法

思路

首先预处理求出树上每个节点的深度，然后较深的一个先往上跳，至两者深度相同，最后两者一起往上跳直到碰面。

时间复杂度

最坏情况是要遍历整棵树，时间复杂度 O(n) 。

倍增

思路

递推方法预处理出每个节点的深度和第 2^i 个祖先。注意利用递推：u 的第 2^i 个祖先等于第 2^{i - 1} 个祖先的第 2^{i - 1} 个祖先。

然后依然是较深一个往上跳，但利用已经预处理的祖先加速向上跳跃的过程。类似快速幂，可以将深度差做二进制展开，然后依据数码 1 的位置往上跳。

最后再两者一起往上跳，同样用祖先方法加速：先找出最小的 k 使得 a_{2^{k}}(u) = a_{2^{k}}(v)，说明最近公共祖先距离不大于 2^k。注意：此时第 2^k 个祖先并不是两者的最近公共祖先，此时可能已经找过头了，需要从 k - 1 往下找。分别令 l =k-1, k-2, \dots, 0，每次都观察是否有 a_{2^l}(u) \ne a_{2^l}(v) 成立，若成立则说明 LCA 在 2^l 个之后，令 u \leftarrow a_{2^l}(u), v \leftarrow a_{2^l}(v)。循环结束后，a_0(u) 必等于 a_0(v)，且 a_0(u) 就是两者的最近公共祖先。

复杂度

空间复杂度 O(n \log n)，使用时最好提前估计一下，开大了容易爆内存。 预处理时间复杂度 O(n \log n + e)，单次查询时间复杂度 O(\log n)。 代码实现上有点类似于 ST 表

代码

const size_t MAXN = 500005;
const size_t MAXLOGN = 30;

// 邻接表存图
struct Edge {
    size_t to;
    size_t next;
} edges[2 * MAXN];

struct Vertex {
    size_t first = 0;
    bool is_visited = false;
} vertices[MAXN];

// 存父节点和深度的结构体
struct TNode {
    size_t fa[MAXLOGN];
    unsigned depth;
} nodes[MAXN];

// BFS 预处理第 2^k 祖先
void bfs(size_t root)
{
    size_t u, v;
    queue<size_t> qu;
    qu.push(root);
    nodes[root].depth = 0;
    // 令根节点的全体祖先节点为自己，方便接下来的处理
    for (size_t k = 0; k < MAXLOGN; k++)
    {
        nodes[root].fa[k] = root;
    }
    while (!qu.empty())
    {
        u = qu.front();
        qu.pop();
        vertices[u].is_visited = true;
        for (size_t e = vertices[u].first; e != 0; e = edges[e].next)
        {
            v = edges[e].to;
            if (!vertices[v].is_visited)
            {
                nodes[v].depth = nodes[u].depth + 1;
                nodes[v].fa[0] = u;
                for (size_t k = 1; k < MAXLOGN; k++)
                {
                    // 第 2^k 个祖先为第 2^(k-1) 个祖先的第 2^(k-1) 个祖先
                    nodes[v].fa[k] = nodes[nodes[v].fa[k - 1]].fa[k - 1];
                }
                qu.push(v);
            }
        }
    }
}

// 查询 a, b 的 LCA
size_t lca(size_t a, size_t b)
{
    if (nodes[a].depth < nodes[b].depth) swap(a, b);
    unsigned diff_depth = nodes[a].depth - nodes[b].depth;
    unsigned cnt = 0;
    // 利用类似快速幂的二进制展开跳至同高度
    while (diff_depth != 0)
    {
        if (diff_depth & 1)
        {
            a = nodes[a].fa[cnt];
        }
        cnt++;
        diff_depth >>= 1;
    }
    if (a == b) return a;
    unsigned k = 0;
    while (nodes[a].fa[k] != nodes[b].fa[k])
    {
        k++;
    }
    // 防止跳过头：只在两者第 2^k 个祖先不同时才跳
    // 祖先相同时可能已经过头了
    while (k)
    {
        k--;
        if (nodes[a].fa[k] != nodes[b].fa[k])
        {
            a = nodes[a].fa[k];
            b = nodes[b].fa[k];
        }
    } 
    return nodes[a].fa[0];
}

Euler 序列

利用 Euler 序列，可以将 LCA 问题转化为区间最值询问（RMQ）问题，从而可以用 ST 表优化到时间 O(1)，或用线段树优化到空间 O(n)。

树链剖分

见 （链接未公开）