学习一下`LCA`算法

最近公共祖先算法

在算法和数据结构的学习中，树结构是一种非常重要且常见的数据结构。在树结构中，节点之间的关系错综复杂，而最近公共祖先（Lowest Common Ancestor，LCA）算法则是解决这些关系的一种关键算法。LCA问题在实际应用中非常广泛，例如家谱树、文件目录树、计算机网络中的路由选择等。

`LCA`算法的定义和应用背景

LCA算法，即最近公共祖先算法，指的是在一棵树中找到两个节点的最近的共同祖先节点。最近公共祖先可以简单地理解为在从这两个节点到根节点的路径中，最深的那个共同节点。

常见应用场景

家谱树: 确定两个家庭成员的最近共同祖先。 ~~找到宇智波佐助和宇智波鼬的最近共同祖先~~
文件目录树: 找出两个文件或目录的最近公共上级目录。
计算机网络: 确定网络节点间的最短路径。

深度优先搜索（`DFS`）在`LCA`算法中的应用

深度优先搜索（DFS）是一种遍历或搜索树或图的算法。DFS从根节点开始，沿着树的深度进行搜索，直到访问所有节点为止。在LCA算法中，DFS用于计算每个节点的深度并记录其祖先信息。

二进制提升（Binary Lifting）方法的原理

二进制提升是一种高效的LCA查询方法。通过预处理，每个节点存储其2^i级祖先的信息，使得在O(log N)时间内可以查询两个节点的LCA。具体方法如下：

使用DFS计算每个节点的深度。
预处理每个节点的$2^i$级祖先。
通过比较两个节点的深度，将它们提升到同一深度，再进行二进制跳跃，找到最近公共祖先。

理论推导及算法复杂度分析

LCA算法的预处理时间复杂度为O(N log N)，查询时间复杂度为O(log N)，其中N为节点数。这样的复杂度使得LCA算法在处理大规模数据时非常高效。

初始化和预处理：构建树结构、深度数组和祖先矩阵

我们首先需要构建树结构，并初始化深度数组和祖先矩阵。通过DFS遍历树，计算每个节点的深度，并填充祖先矩阵。

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,s,a,b;
vector <int> e[N];
int dep[N],fa[N][20];
void dfs(int x,int father){
    dep[x]=dep[father]+1;
    fa[x][0]=father;
    for(int i=1;i<=19;i++){
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(int y:e[x])
        if(y!=father)dfs(y,x);
}

int lca (int x,int y){
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i=19;i>=0;i--){
        if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
    }
    if(x==y) return y;
    
    for(int i=19;i>=0;i--){
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}

int main (){
    int a,b;
    cin>>n>>m>>s;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(s,0);
    int cnt=0,ans[500005];
    while(m--){
        cin>>a>>b;
        ans[cnt]=lca(a,b);
        cnt++;
    }
    for(int i=0;i<cnt;i++){
        cout<<ans[i]<<endl;
    }
}

代码解析

定义和初始化：首先定义了节点数、边数、根节点以及其他辅助变量。
DFS函数：通过DFS计算每个节点的深度，并预处理其祖先信息。
LCA函数：使用二进制提升方法查询两个节点的最近公共祖先。
主函数：读入数据，构建树结构，调用DFS进行预处理，最后处理每个查询并输出结果。

学习一下LCA算法