最近公共祖先

最近公共祖先（Lowest Common Ancestor，LCA）是指兩個或多個節點在一棵樹中共有的祖先節點中深度最低的那個。在算法競賽中，LCA是一種常用的問題，在樹上進行相關操作的時候，LCA可以有效提高算法的效率。

一、基本概念

在樹中，從根節點向下走到節點$p$和$q$，假設它們之間任意一條路徑上的最後一個公共節點為$x$，則$x$是$p$和$q$的公共祖先。如果一個節點是它自己的祖先，那麼它就是公共祖先中深度最低的那個，也就是最近公共祖先。

二、求解LCA的方法

1.暴力枚舉法

暴力枚舉算法的做法是，對於每一對需要查找LCA的節點$p$和$q$，從$p$依次向上遍歷祖先，直到找到某個祖先節點$u$，使得$u$是$q$的祖先。這樣，找到的節點$u$就是$p$和$q$的最近公共祖先。這種算法的時間複雜度為$O(n^2)$。

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};
using p = pair;

TreeNode* LCA(TreeNode* root, TreeNode* p, TreeNode* q){
    function isAncestor = [](TreeNode* p, TreeNode* q){
        if(p == nullptr) return false;
        if(p == q) return true;
        return isAncestor(p->left, q) || isAncestor(p->right, q);
    };
    queue q;    q.push({root, -1});    vector
 tmp;    while(!q.empty()){        int n = q.size();        while(n--){            auto [cur, parent] = q.front();            q.pop();            tmp.emplace_back(cur, parent);            if(cur->val == p->val || cur->val == q->val){                if(tmp.size() == 1) return cur;                break;            }            if(cur->left){                q.push({cur->left, cur->val});            }            if(cur->right){                q.push({cur->right, cur->val});            }        }        if(isAncestor(tmp.back().first, p) && isAncestor(tmp.back().first, q)) continue;        while(tmp.size()){            auto [cur, _] = tmp.back();            tmp.pop_back();            if(isAncestor(cur, p) && isAncestor(cur, q)) return cur;        }    }    return nullptr;}

2. 深度優先搜索法

在對樹進行深度優先搜索（DFS）的時候，記錄下每個節點的深度和父節點，如果需要查找節點$p$和$q$的LCA，對於節點$p$和$q$，沿着樹分別向上找到它們的祖先節點，一直找到它們的深度相等，這樣的節點就是它們的最近公共祖先。

// 建立 parent 和 depth 數組
void dfs(int u, int p, int d){
    parent[u] = p;
    depth[u] = d;
    for(auto v : g[u]){
        if(v != p){
            dfs(v, u, d + 1);
        }
    }
}

// 求解LCA
int LCA(int u, int v){
    int du = depth[u];
    int dv = depth[v];
    while(du > dv){
        u = parent[u];
        du--;
    }
    while(dv > du){
        v = parent[v];
        dv--;
    }
    while(u != v){
        u = parent[u];
        v = parent[v];
    }
    return u;
}

3.倍增法

針對較大規模的樹，在求解LCA時暴力枚舉的時間複雜度太高，可採用倍增法。倍增法的思路是，預處理出每個節點往上跳$2^k$個節點後能到達的節點，從而減少查找LCA的時間複雜度，使之變為$O(logn)$。具體實現時，需要預處理一個$fa[i][j]$數組，表示從節點$i$開始往上跳$2^j$個節點所能到達的節點編號。同時，還需要預處理一個$depth[i]$數組，表示節點$i$的深度。

// 節點編號從`0`開始
const int MAXN = 1e5 + 10;
int depth[MAXN], fa[MAXN][21];

// 預處理深度和預處理fa數組
void dfs(int u, int p, int d){
    depth[u] = d;
    fa[u][0] = p;
    for(int i = 1; (1 << i) < MAXN; ++i){
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for(auto v : g[u]){
        if(v != p){
            dfs(v, u, d + 1);
        }
    }
}

// 求解LCA
int LCA(int u, int v){
    if(depth[u] = 0; --i){
        if(depth[u] - (1 <= depth[v]){
            u = fa[u][i];
        }
    }
    if(u == v) return u;
    for(int i = log2(depth[u]); i >= 0; --i){
        if(fa[u][i] != fa[v][i]){
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}