#创作计划# LCA的求法

Srobot

2025-11-30 17:39:02

发布于：广东

13阅读

0回复

0点赞

一、定义

$LCA$ 指的是最近公共祖先。一般来说，假如有一棵有根树，存在结点 $x$ 和结点 $y$ ，若结点 $z$ 是结点 $x$ 的祖先，也是结点 $y$ 的祖先，则称结点 $z$ 为结点 $x$ 和结点 $y$ 的公共祖先。这 $2$ 个结点深度最大的公共祖先被称为最近公共祖先，记为 $LCA(x,y)$ 。

如图，若结点 $1$ 为根结点，则 $LCA(3,5)=2$ ， $LCA(5,6)=1$ 。

二、求解 $LCA$

我们首先考虑如何“暴力”求解 $2$ 个结点的 $LCA$ 。

容易想到，可以先 $DFS$ 一遍找出每个结点的深度 $deep$ ，如果要求 $LCA(2,6)$ ，先从深度大的结点 $6$ 往上跳至其父结点 $4$ ，发现深度与结点 $2$ 一样了，但还是不在同一个结点，此时结点 $2$ 和结点 $4$ 一起往上跳，到达共同的父结点 $1$ ，得到 $LCA(2,6)=1$ 。
但是这个方法在最坏情况下时间复杂度为 $O(n)$ ，数据规模大时容易 $TLE$ 。

三、优化暴力

仔细思考便会发现，这个方法慢就慢在是一步一层往上跳的，如果能一步往上多跳几层，效率自然就高了。
我们采用树上倍增法，设 $f[x][k]$ 表示结点 $x$ 的 $2^k$ 辈祖先，即从结点 $x$ 出发向根结点走 $2^k$ 步到达的结点。若该结点不存在，则另 $f[x][k]=0$ 。这类似于动态规划，状态转移方程为 $f[x][k]=f[f[x][k-1]][k-1]$ ，边界条件即 $f[x][0]$ 为结点 $x$ 的父结点。
以上是预处理，时间复杂度为 $O(nlogn)$ ，之后对于每个 $LCA(x,y)$ ，都可以在 $O(logn)$ 时间内计算出来。

基于 $f$ 数组计算 $LCA(x,y)$ 分为以下几步：

设 $dep[x]$ 表示结点 $x$ 的深度，可令 $dep[x]≥dep[y]$ （否则就交换 $x$ 和 $y$ ）
接下来，依次尝试令 $k=2^{log\ n},2^{log\ n-1},...,2^1,2^0$ ，直到满足 $dep[f[x][k]]≥dep[y]$ ，令 $x=f[x][k]$
若此时 $x=y$ ，则 $LCA(x,y)=x$ ，否则，依次尝试令 $k=2^{log\ n},2^{log\ n-1},...,2^1,2^0$ ，直到满足 $f[x][k]≠f[y][k]$ ，令 $x=f[x][k],y=f[y][k]$ ，这时 $x$ 和 $y$ 必定只差 $1$ 步便相遇了， $LCA(x,y)=f[x][0]$ 。

具体代码实现如下：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int N = 1e6 + 10;
const int LOG = 20; // 最大深度对数

int f[N][LOG];
struct tree {
    int dep = 1; // 该结点的深度
    vector<int> k; // 存储边的邻接表
    int fa = 0;  // 该结点的父结点
} a[N]; // 表示结点的结构体

void dfs(int t) { // 预处理出每个结点的深度和其父结点
    vector<int> q = a[t].k;
    for (int i = 0; i < q.size(); i++) {
        if (a[q[i]].fa > 0 || q[i] == 1)
            continue;
        a[q[i]].dep = a[t].dep + 1;
        a[q[i]].fa = t;
        dfs(q[i]);
    }
}

int lca(int x, int y) {
    // 确保x的深度不小于y的深度
    if (a[x].dep < a[y].dep) {
        swap(x, y);
    }
    
    // 将x提升到与y同一深度
    for (int k = LOG - 1; k >= 0; k--) {
        if (a[f[x][k]].dep >= a[y].dep) {
            x = f[x][k];
        }
    }
    
    // 如果此时x等于y，则y就是LCA
    if (x == y) {
        return x;
    }
    
    // 同时向上跳，直到父节点相同
    for (int k = LOG - 1; k >= 0; k--) {
        if (f[x][k] != f[y][k]) {
            x = f[x][k];
            y = f[y][k];
        }
    }
    
    // 返回LCA
    return f[x][0];
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 读入树结构
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        a[u].k.push_back(v);
        a[v].k.push_back(u);
    }
    
    // 预处理深度和父结点
    dfs(1);
    
    // 初始化f数组
    for (int i = 1; i <= n; i++) {
        f[i][0] = a[i].fa;
    }
    
    // 构建倍增数组
    for (int k = 1; k < LOG; k++) {
        for (int i = 1; i <= n; i++) {
            if (f[i][k-1] > 0) {
                f[i][k] = f[f[i][k-1]][k-1];
            } else {
                f[i][k] = 0;
            }
        }
    }
    
    // 处理查询
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        int result = lca(x, y);
        cout << "结点 " << x << " 和结点 " << y << " 的LCA是: " << result << endl;
    }
    
    return 0;
}