最近公共祖先

最近公共祖先（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] < depth[v]) swap(u, v);
    for(int i = log2(depth[u]); i >= 0; --i){
        if(depth[u] - (1 << i) >= 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];
}

三、总结

求解树上两个节点的最近公共祖先是树相关算法中的重要问题。根据不同的应用场景和需求，可以选择不同的LCA算法，如暴力枚举、深度优先搜索和倍增法等。在实际应用中，需要根据数据规模和时间复杂度的要求，选择合适的算法。