P3379 【模板】最近公共祖先（LCA）

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接的最近公共祖先。

输入格式

第一行包含三个正整数 $N,M,S$，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 $N-1$ 行每行包含两个正整数 $x, y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成一棵树）。

接下来 $M$ 行每行包含两个正整数 $a, b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。

输出格式

输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。

输入输出样例 #1

输入 #1

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出 #1

4
4
1
4
4

说明/提示

对于 $30\%$ 的数据，$N \le 10$，$M \le 10$。

对于 $70\%$ 的数据，$N \le 10000$，$M \le 10000$。

对于 $100\%$ 的数据，$1 \le N,M \le 500000$，$1 \le x,y,a,b \le N$，不保证 $a \neq b$。

样例说明：

该树结构如下：

        4
       / \
      2   1
         / \
        3   5

• 2 和 4 的最近公共祖先是 4。
• 3 和 2 的最近公共祖先是 4。
• 3 和 5 的最近公共祖先是 1。
• 1 和 2 的最近公共祖先是 4。
• 4 和 5 的最近公共祖先是 4。

知识点：最近公共祖先，$lca$ 算法，树上倍增算法

**最近公共祖先（$lca$）**指在一棵有根树中，两个节点 $u$ 和 $v$ 深度最大（距离最近）的公共祖先，记为 $lca(u, v)$。

$lca$ 算法（这里主要指树上倍增算法）是求最近公共祖先的一种很优秀的算法。树上倍增算法 本质上是利用了二进制拆分和动态规划（预处理 $st$ 表）的思路。

如果采用未经优化的暴力跳法，即先把深度较深的节点一步一步向上跳到同一深度，然后再同时一步一步向上跳直到相遇，最坏情况下时间复杂度为 $O(n * m)$，复杂度太大。

因此考虑用倍增优化的方式降低复杂度。定义 fa[u][i] 表示节点 $u$ 向上跳 $2^i$ 步到达的祖先节点。因为跳 $2^i$ 步相当于先跳 $2^{i-1}$ 步，再跳 $2^{i-1}$ 步，所以状态转移方程（预处理 fa 数组）为：

fa[u][i] = fa[fa[u][i - 1]][i - 1];

倍增 $lca$ 算法 的核心思想分为以下几步：

1. $dfs$ 过程：从根节点 $rt$ 开始遍历，递归更新每个节点的深度 dep[u] 和父节点 fa[u][0]。
2. 预处理 $st$ 表（fa 数组）：枚举次方 $j$ 从 $1 \sim 19$，节点 $i$ 从 $1 \sim n$，预处理出所有 fa[i][j]。时间复杂度为 $O(n * \log n)$。
3. 查询 $lca$：
   • 找到深度更深的节点（假设为 $v$），求出深度差 $d = dep[v] - dep[u]$。
   • 利用二进制拆分（(d >> i) & 1），让 $v$ 一下子跳到和 $u$ 相同的深度。
   • 如果跳完后 $u == v$，说明 $u$ 就是 $v$ 的祖先，直接返回 $u$。
   • 否则，两个节点同时向上跳 $2^i$ 步（从大到小尝试 $i = 19 \sim 0$）。当 fa[u][i] != fa[v][i] 时，说明还没有跳到最近公共祖先或刚到下方，此时更新 u = fa[u][i] 和 v = fa[v][i]；如果相等则不跳。
   • 最后，$u$ 和 $v$ 会停在 $lca$ 的下一层，答案就是 fa[u][0]。

PS：树上倍增预处理时间复杂度为 $O(n * \log n)$，单次查询时间复杂度为 $O(\log n)$，空间复杂度一般较小。

分析

此题没有太多的变种，就是纯 $lca$ 树上倍增算法的模板。

1. 树上 DFS：从给定的根节点 $rt$ 开始 $dfs$，递归更新节点的深度 dep[u] 和直接父节点 fa[u][0]（注意跳过父节点 if (v == fath) continue;，防止死循环）。
2. 倍增数组初始化：预处理 fa 数组时，外层循环必须枚举 $j$（次方），内层循环枚举 $i$（节点），因为 fa[i][j] 依赖于 fa[...][j-1]。
3. 查询 LCA：在 solve() 函数中，如果 $a == b$ 可以直接特判输出 $a$；否则利用二进制拆分先对齐深度，再双指针同时向上跳寻找最近公共祖先。

PS：注意树是双向边/无向边，存图时用 vector <ll> vc[maxn] 建双向边。

代码

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fLL
using namespace std;

const ll maxn = 5e5 + 5;
ll n , m , rt;
ll dep[maxn] , ans = -inf;
ll fa[maxn][20];
vector <ll> vc[maxn];

void dfs (ll u , ll fath) {
    fa[u][0] = fath;
    //更新节点深度
    dep[u] = dep[fath] + 1;
    for (auto v : vc[u]) {
        //是v == fath！
        if (v == fath) continue;
        //递归
        dfs(v , u);
    }
}

ll lca (ll v , ll u) {
    if (dep[v] < dep[u]) swap(u , v);
    //深度差
    ll d = dep[v] - dep[u];
    //先跳到相同的深度并判断
    for (ll i = 19; i >= 0; i--) {
        if ((d >> i) & 1) {
            v = fa[v][i];
        }
    }
    //两个节点同时向上跳，找到最近的公共祖先
    if (u == v) return u;
    for (ll i = 19; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

void solve () {
    ll a , b;
    cin >> a >> b;
    if (a == b) {
        cout << a << endl;
        return;
    }
    cout << lca(a , b) << endl;
}

int main () {
    cin >> n >> m >> rt;
    //存树
    for (ll i = 1; i <= n - 1; i++) {
        ll x , y;
        cin >> x >> y;
        vc[x].push_back(y);
        vc[y].push_back(x);
    }
    dep[rt] = 0;
    //计算深度
    dfs(rt , 0);
    //预处理st表(fa数组)
    for (ll j = 1; j <= 19; j++) {
        for (ll i = 1; i <= n; i++) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    while (m--) solve();
    return 0;
}