(树) 最近公共祖先（LCA）

前言

如这个问题的名字一样，我们的目的是为了求得一个树上两个点得最近公共祖先

通常对于树的操作那自然是离不开搜索，其中dfs的理解和编写必须了熟于心

解决LCA的算法常见的有三种，Tarjan，树链剖分，倍增算法

参考资料：

321 最近公共祖先 倍增算法_哔哩哔哩_bilibili

322 最近公共祖先 Tarjan算法_哔哩哔哩_bilibili

323 最近公共祖先 树链剖分_哔哩哔哩_bilibili

下表也是董晓老师整理

	倍增算法	Tarjan算法	树链剖分
数据结构	fa[][], dep[]	fa[], vis[], query[], ans[]	fa[], dep[], sz[], son[], top[]
算法	倍增法 深搜打表，跳跃查询	并查集 深搜， 回时指父， 离时搜根	重链剖分 两遍深搜打表，跳跃查询
时间复杂度	$O((n+m)logn)$	$O(n+m)$	$O(n+mlogn)$

---

其中，倍增算法的效率偏低些

Tarjan是离线算法

树链剖分需要dfs两次

可以说每种算法都各有特点

练习题：

本文代码针对本题：洛谷：P3379 【模板】最近公共祖先（LCA）

杭电：2586 How far away ？ 本题是带有权值的

具体算法

Tarjan

Tarjan专题：(图论) Tarjan 算法_天赐细莲的博客-CSDN博客_tarjan算法

Tarjan 是一种离线算法

这里巧妙利用到了并查集的帮助

先记录所有的查询状态，强制转化为离线算法

在每次dfs完子节点后，让子节点的并查集指向当前节点 (子->父)

在当前节点dfs完毕后，检查搜索集，是否有对应的查询点

若存在，且已经访问过，则表示对应点的并查集已经记录了

此时可以记录对应查询组的lca，注意这里一定要写路径压缩的并查集

因为我们可以通过不断的压缩，将并查集的指向不断的往树的上方指

最终确保压缩到目标的lca

/** * https://www.luogu.com.cn/problem/P3379 * P3379 【模板】最近公共祖先（LCA） * Tarjan */
#include <bits/stdc++.h>
using namespace std;

const int M = 10 + 5 * 100000;
vector<vector<int>> graph(M);             // 存图（树）
vector<vector<pair<int, int>>> query(M);  // 询问

int father[M];  // 并查集
bool vis[M];    // vis
int ans[M];     // 第几组询问的答案

void initUnionFind(int n) {
    
    for (int i = 0; i <= n; i++) {
    
        father[i] = i;
    }
}
// 必须路径压缩
int unionFind(int x) {
    
    return x == father[x] ? x : father[x] = unionFind(father[x]);
}

// Tarjan 算法
void Tarjan(int cur) {
    
    vis[cur] = true;
    for (int& nex : graph[cur]) {
    
        if (!vis[nex]) {
    
            Tarjan(nex);
            // 核心 nex 指向 cur
            father[nex] = cur;
        }
    }
	// 递归完毕
    for (auto& it : query[cur]) {
    
        int &to = it.first, &idx = it.second;
        // 若访问过，则可以记录
        if (vis[to]) {
    
            ans[idx] = unionFind(to);
        }
    }
}

int main() {
    
    // 边数 询问数 根节点
    int n, m, root;
    scanf("%d %d %d", &n, &m, &root);
    // 初始化并查集
    initUnionFind(n);

    // 存无向图
    for (int i = 1, u, v; i <= n - 1; i++) {
    
        scanf("%d %d", &u, &v);
        graph[v].emplace_back(u);
        graph[u].emplace_back(v);
    }

    // 离线算法，先知道所有情况，再算
    // 询问 也要双向存
    for (int i = 1, x, y; i <= m; i++) {
    
        scanf("%d %d", &x, &y);
        query[x].emplace_back(y, i);
        query[y].emplace_back(x, i);
    }

    Tarjan(root);

    for (int i = 1; i <= m; i++) {
    
        printf("%d\n", ans[i]);
    }

    return 0;
}

树链剖分

树链剖分 分为很多种，这里写的是重链剖分

这里的重表示的是当前树的节点的数量

当某个子树的数量是所有子树中最多的时候，这个节点就是所谓的重孩子

那么当前点就是这个重子树中所有点的重链头

其余的子树再单独自立门户开辟重链

在求lca时，不断靠着链头节点的跳跃，跨过大量的节点

dfs1()

主要获得son[], father[], deep[] 其中size[]是辅助搜索出son[]用的

dfs2()

借助son[]和father[]求出top[]（重链的头）

lca()

首先明确一点，重链头的链头节点就是本身

不断判断两个点的链头是否相等

若不等则让深度更深的点跳跃到链头的父节点

这样深点就能向根节点靠近很多，且能更新到新的链中，可以重新判断了

最终，当两者的链头相等时候，返回深度较低的点，获得lca

/** * https://www.luogu.com.cn/problem/P3379 * P3379 【模板】最近公共祖先（LCA） * 树链剖分 (重链) */
#include <bits/stdc++.h>
using namespace std;

const int M = 10 + 5 * 100000;

vector<vector<int>> graph(M);  // 图
vector<int> father(M);         // 父节点
vector<int> son(M);            // 重孩子
vector<int> size(M);           // 子树节点个数
vector<int> deep(M);           // 深度，根节点为1
vector<int> top(M);            // 重链的头，祖宗

void dfs1(int cur, int from) {
    
    deep[cur] = deep[from] + 1;  // 深度，从来向转化来
    father[cur] = from;          // 父节点，记录来向
    size[cur] = 1;               // 子树的节点数量
    son[cur] = 0;                // 重孩子 (先默认0表示无)

    for (int& to : graph[cur]) {
    
        // 避免环
        if (to == from) {
    
            continue;
        }
        // 处理子节点
        dfs1(to, cur);
        // 节点数量叠加
        size[cur] += size[to];
        // 松弛操作，更新重孩子
        if (size[son[cur]] < size[to]) {
    
            son[cur] = to;
        }
    }
}

void dfs2(int cur, int grandfather) {
    
    top[cur] = grandfather;  // top记录祖先
    // 优先dfs重儿子
    if (son[cur] != 0) {
    
        dfs2(son[cur], grandfather);
    }
    for (int& to : graph[cur]) {
    
        // 不是cur的父节点，不是重孩子
        if (to == father[cur] || to == son[cur]) {
    
            continue;
        }
        // dfs轻孩子
        dfs2(to, to);
    }
}

int lca(int x, int y) {
    
    // 直到top祖宗想等
    while (top[x] != top[y]) {
    
        // 比较top祖先的深度，x始终设定为更深的
        if (deep[top[x]] < deep[top[y]]) {
    
            swap(x, y);
        }
        // 直接跳到top的父节点
        x = father[top[x]];
    }
    // 在同一个重链中，深度更小的则为祖宗
    return deep[x] < deep[y] ? x : y;
}

int main() {
    
    // 边数 询问数 根节点
    int n, m, root;
    cin >> n >> m >> root;

    // 该树编号 [1, n]
    // 本题仅仅说有边，未说方向
    for (int i = 1, u, v; i <= n - 1; i++) {
    
        cin >> u >> v;
        graph[v].emplace_back(u);
        graph[u].emplace_back(v);
    }

    // 树链剖分 重链
    dfs1(root, 0);
    dfs2(root, root);

    for (int i = 1, x, y; i <= m; i++) {
    
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }

    return 0;
}

倍增算法

倍增cin, cout不能过

倍增算法 本质是一种借助二进制的动态规划，而这里又是对树的操作，也可以说是一道树形dp了

通常定义father[i][j]表示i到j的状态，而这里倍增的j指的是2的倍数

即2^j，以二进制成倍的增加，这就是所谓的倍增

dfs

这里的dfs主要是以深度来进行倍增

由父亲跳到爷爷，由爷爷跳到高祖父

由于是dfs我们可以先处理辈分高的节点

之后的递归可以借助已经处理的高辈分节点来打倍增表

lca

这里的搜索主要也是通过将高深度拉回低深度的方式处理

先处理两者中的高深度节点

由于任何一个十进制数都能分解成二进制，因此必然能跳走我们需要的距离

我们先跳大步，在跳小步可以保证跑一遍循环就能达到我们的目标位置

跳完后先特判走两个节点重合的情况

此时，两个点的高度是相等的，那就两者一起往上跳。

注意我们只能一起跳到lca的下一层节点

若继续跳下去，最后必然是一起跳到root，那就没有任何意义了

/** * https://www.luogu.com.cn/problem/P3379 * P3379 【模板】最近公共祖先（LCA） * 倍增算法 * cin cout 超时 */
#include <bits/stdc++.h>
using namespace std;

const int M = 10 + 100000 * 5;
// log2(5e5 + 10) = 18.9
vector<vector<int>> graph(M);                    // 存图
vector<int> deep(M);                             // 深度
vector<vector<int>> father(M, vector<int>(20));  // i点跳2^j步到达的点(点号)

void dfs(int cur, int from) {
    
    deep[cur] = deep[from] + 1;  // 深度 + 1
    father[cur][0] = from;       // 跳2^0=1步就是直接的父节点

    // 借助上一层的父节点跳到爷爷节点
    int log = log2(M + 1);
    for (int i = 1; i <= log; i++) {
    
        father[cur][i] = father[(father[cur][i - 1])][i - 1];
    }

    for (int& nex : graph[cur]) {
    
        if (nex == from) {
    
            continue;
        }
        dfs(nex, cur);
    }
}

int lca(int u, int v) {
    
    // u设为深度大的点，对u进行跳步
    if (deep[u] < deep[v]) {
    
        swap(u, v);
    }

    // 计算一下深度，过滤掉部分循环
    // +1保精度
    int log = log2(deep[u] + 1);

    // 二进制拆分，先跳大步
    // 将深度大的跳到同一深度
    for (int i = log; i >= 0; i--) {
    
        if (deep[father[u][i]] >= deep[v]) {
    
            u = father[u][i];
        }
    }
    // v正好是u的lca，可以直接return
    if (u == v) {
    
        return v;
    }
    for (int i = log; i >= 0; i--) {
    
        // 有父节点，才可能跳
        // 实际可以省略，因为是同层，都是0则if为false
        // 父节点不同则要跳
        if (father[u][i] != 0 && father[u][i] != father[v][i]) {
    
            u = father[u][i];
            v = father[v][i];
        }
    }
    // 退出循环时，保证两个点在lca的正下方同一层
    return father[u][0];
}

int main() {
    
    // 边数 询问数 根节点
    int n, m, root;
    scanf("%d %d %d", &n, &m, &root);

    // 该树编号 [1, n]
    // 本题仅仅说有边，未说方向
    for (int i = 1, u, v; i <= n - 1; i++) {
    
        scanf("%d %d", &u, &v);
        graph[v].emplace_back(u);
        graph[u].emplace_back(v);
    }

    // 预处理倍增的father[i][2^j]和deep[]
    dfs(root, 0);

    for (int i = 1, x, y; i <= m; i++) {
    
        scanf("%d %d", &x, &y);
        printf("%d\n", lca(x, y));
    }

    return 0;
}

---

---

---

END