最近公共祖先詳解

一、定位概念

最近公共祖先（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 = 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]  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問題是計算機科學中一種常見的算法問題，在實際生活中有廣泛的應用。

基礎算法的核心思想是遍歷整棵樹，記錄節點的祖先列表，計算節點的深度，比較兩個節點的祖先列表，找到最後一個相同的節點即為最近公共祖先。

改善算法的核心思想是預處理出每個節點到根節點的距離，使用二分查找的方法，找到兩個節點深度最淺的公共祖先，達到了比基礎算法更高效的效果。