最近公共祖先详解

一、定位概念

最近公共祖先（LCA），指的是在一个树或有向无环图中，找到两个节点的共同祖先中深度最小的一个。

LCA问题是计算机科学中一种常见的算法问题，它有着广泛的应用。例如，可以用来处理家谱信息，或者解决大多数其他相关问题，例如计算两个版本之间的最近公共祖先或两个字符串之间的LCS（最长公共子序列）等等。

二、基本算法

LCA问题的本质是求树中两个节点的最近公共祖先，最简单的算法是遍历整棵树，记录下每个节点的祖先，比较两个节点的祖先列表，找到最后一个相同的节点即为最近公共祖先。该算法的时间复杂度为O(N^2)，其中N为节点的数量。

#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, root; //输入数据：n表示树的节点数量，m表示询问数量，u、v表示两个节点
vector<int> adj[10001]; //存储树的连接关系
vector<int> parents[10001]; //存储每个节点的祖先
void dfs(int u, int p) { //深度优先遍历
    parents[u].push_back(p);
    for (auto v : adj[u]) {
        if (v != p) dfs(v, u);
    }
}
int lca(int u, int v) { //计算最近公共祖先
    if (parents[u].size() > parents[v].size()) swap(u, v);
    int len1 = parents[u].size();
    int len2 = parents[v].size();
    for (int i = 0; i < len2 - len1; i++) v = parents[v][len2 - 2 - i];
    for (int i = len1 - 1; i >= 0; i--) {
        if (parents[u][i] == parents[v][i]) return parents[u][i];
    }
    return root;
}
int main() {
    scanf("%d%d%d", &n, &m, &root);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(root, 0); //预处理每个节点的祖先
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}

三、改善算法

遍历整棵树是一种时间复杂度比较高的算法，可以对其进行改善，以达到更好的效果。改善算法的核心思想是预处理出每个节点到根节点的距离，然后通过二分查找的方法，找到两个节点深度最浅的公共祖先。

#include <bits/stdc++.h>
using namespace std;
const int N = 10001;
int n, m, u, v, root, depth[N], f[N][16]; //f数组用于辅助计算节点的距离
vector<int> adj[N];
void dfs(int u, int p) { //深度优先遍历，预处理每个节点的深度和父节点
    depth[u] = depth[p] + 1;
    f[u][0] = p;
    for (int i = 1; (1 << i) <= depth[u]; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1]; //使用DP的思想，把节点的距离预处理出来
    }
    for (auto v : adj[u]) {
        if (v != p) dfs(v, u);
    }
}
int lca(int u, int v) { //利用二分查找的思想，计算最近公共祖先
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int i = 0; diff > 0; i++) {
        if (diff & 1) u = f[u][i];
        diff >>= 1;
    }
    if (u == v) return u;
    for (int i = log2(depth[u]); i >= 0; i--) {
        if (f[u][i] != f[v][i]) {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}
int main() {
    scanf("%d%d%d", &n, &m, &root);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(root, 0);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}

四、总结

本文从概念、基本算法和改善算法三个方面进行了LCA问题的详细阐述。LCA问题是计算机科学中一种常见的算法问题，在实际生活中有广泛的应用。

基础算法的核心思想是遍历整棵树，记录节点的祖先列表，计算节点的深度，比较两个节点的祖先列表，找到最后一个相同的节点即为最近公共祖先。

改善算法的核心思想是预处理出每个节点到根节点的距离，使用二分查找的方法，找到两个节点深度最浅的公共祖先，达到了比基础算法更高效的效果。