专栏文章

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

mmazhenhao0235
P3379题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipt7hs7
此快照首次捕获于
2025/12/03 17:33
3 个月前
此快照最后确认于
2025/12/03 17:33
3 个月前
查看原文

一、LCA问题概述

最近公共祖先（Lowest Common Ancestor ，简称 LCA）是树结构中的一个基本问题，指在一棵有根树中，两个节点的公共祖先中深度最大的那个节点。 LCA 问题在树结构相关算法中有着广泛的应用，如计算树上两点间路径、解决树上的查询问题等。

二、多种 LCA 求解算法详解

1.朴素算法（暴力跳转法）

基本思路：
  • 将两个节点调整到同一深度
  • 然后同时向上跳转，直到相遇
实现步骤：
  1. 计算两个节点的深度差
  2. 较深的节点向上跳转深度差步
  3. 两个节点同时向上跳转，直到相遇
复杂度分析：
  • 预处理：无（或 O(n)O(n) 计算深度）
  • 查询：最坏 O(n)O(n)
优缺点：
  • 优点：实现简单
  • 缺点：查询效率低，不适用于大规模数据

2. 倍增算法

基本思路：
  • 预处理每个节点向上 2k2^k 层的祖先
  • 利用二进制拆分思想快速跳转
实现步骤：
1.预处理每个节点的 2k2^k 级祖先
2.查询时先将两个节点调整到同一深度
3.然后尝试以 2k2^k 的步长向上跳转
关键代码：
CPP
int LCA(int x, int y) {
    if(dep[x] < dep[y]) swap(x,y);
    for(int i=20; i>=0; i--)
        if(dep[fa[x][i]] >= dep[y])
            x = fa[x][i];
    if(x == y) return x;
    for(int i=20; i>=0; i--)
        if(fa[x][i] != fa[y][i])
            x=fa[x][i], y=fa[y][i];
    return fa[x][0];
}
复杂度分析：
  • 预处理 O(nlogn)O(nlogn)
  • 查询 O(logn)O(logn)
优缺点：
  • 优点：查询效率高
  • 缺点：预处理空间复杂度较高

3. Tarjan离线算法

基本思路：
  • 利用并查集和 DFS 遍历
  • 离线处理所有查询
实现步骤：
  1. 对树进行 DFS 遍历
  2. 使用并查集维护已访问节点
  3. 在处理完一个节点的子树后，处理与该节点相关的查询
复杂度分析：
  • 时间复杂度： O(nα(n))O(nα(n)) （近似线性）
  • 需要离线处理所有查询
优缺点：
  • 优点：时间复杂度优秀
  • 缺点：必须离线处理，实现较复杂

4. 树链剖分算法（本题解法）

基本思想：
  • 将树划分为若干条链
  • 利用链的性质加速查询
核心概念：
  • 重儿子：子树大小最大的儿子
  • 轻儿子：其他儿子
  • 重链：由重儿子连接形成的链
实现步骤：
第一次 DFS ：
CPP
void dfs1(int u, int fat) {
    siz[u] = 1;                  // 初始化子树大小为1
    dep[u] = dep[fat] + 1;       // 计算深度
    fa[u] = fat;                 // 记录父节点
    for(auto v : g[u]) {
        if(v == fat) continue;
        dfs1(v, u);
        siz[u] += siz[v];        // 累加子树大小
        if(siz[v] > siz[heavy[u]]) 
            heavy[u] = v;        // 更新重儿子
    }
}
第二次 DFS ：
CPP
void dfs2(int u, int tp) {
    top[u] = tp;                 // 记录链顶
    dfn[u] = ++idx;              // 记录DFS序
    if(!heavy[u]) return;        // 叶子节点返回
    
    dfs2(heavy[u], tp);          // 优先处理重儿子（保证重链连续）
    for(auto v : g[u])
        if(v != fa[u] && v != heavy[u])
            dfs2(v, v);          // 轻儿子作为新链的起点
}
LCA查询
CPP
int LCA(int x, int y) {
    while(top[x] != top[y]) {    // 当两个节点不在同一条链上
        if(dep[top[x]] < dep[top[y]]) 
            swap(x, y);          // 选择链顶较深的链
        x = fa[top[x]];         // 跳到链顶的父节点
    }
    return dep[x] < dep[y] ? x : y; // 返回深度较小的节点
}
复杂度分析：
  • 预处理：两次 DFS ， O(n)O(n)
  • 查询： O(logn)O(logn) （因为树被剖分成 O(logn)O(logn) 条链
优势：
  • 预处理时间与空间复杂度优秀
  • 查询效率高且稳定
  • 可以同时支持其他树路径操作

完整代码

CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m, s, u, v, x, y;
int siz[N], heavy[N], fa[N], top[N], dep[N];
vector<int> g[N];

void dfs1(int u, int fat) {
    siz[u] = 1;
    dep[u] = dep[fat] + 1;
    fa[u] = fat;
    for(auto v : g[u]) {
        if(v == fat) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[heavy[u]]) heavy[u] = v;
    }
}

void dfs2(int u, int tp) {
    top[u] = tp;
    if(!heavy[u]) return;
    dfs2(heavy[u], tp);
    for(auto v : g[u])
        if(v != fa[u] && v != heavy[u]) dfs2(v, v);
}

int LCA(int x, int y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for(int i = 1; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(s, 0);
    dfs2(s, s);
    while(m--) {
        cin >> x >> y;
        cout << LCA(x, y) << '\n';
    }
    return 0;
}

算法核心思想

树链剖分通过将树分解为多条链来加速 LCA 查询。其核心在于：
  1. 重链剖分：将树划分为若干条"重链"，使得从任意节点到根的路径最多经过 O(logn)O(logn) 条链
  2. 跳跃查询：通过在这些链上跳跃，快速找到 LCA

总结

树链剖分是解决LCA问题的高效算法，通过两次DFS预处理将树划分为重链，使得每次查询可以在 O(logn) O(logn) 时间内完成。相比倍增算法，它的预处理时间更优（ O(n)O(n) vs O(nlogn)O(nlogn) ） ，且实际运行效率更高。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...