最近公共祖先（LCA）

• 学习算法——最近公共祖先

• 算法介绍：LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科

• 例题：洛谷-LCA模板题

• 模板代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 500005;
struct node{
    int t,nex;
};
node a[maxn<<1];
int head[maxn],tot;
void add(int x,int y){
    a[++tot].t = y,a[tot].nex = head[x],head[x] = tot;
}

int depth[maxn],fa[maxn][30],lg[maxn];
void dfs(int x,int fath)
{
    fa[x][0] = fath,depth[x] = depth[fath] + 1;
    for(int i=1;i<=lg[depth[x]];i++)
        fa[x][i] = fa[fa[x][i-1]][i-1];
    for(int i=head[x] ; i ; i = a[i].nex)
        if(a[i].t != fath)
            dfs(a[i].t , x);
}
int lca(int x,int y)
{
    if(depth[x] < depth[y])swap(x,y);
    while(depth[x] > depth[y])
        x = fa[x][lg[depth[x]-depth[y]] -1];
    if(x == y)
        return x;
    for(int k=lg[depth[x]] - 1;k>=0;k--)
        if(fa[x][k] != fa[y][k])
            x = fa[x][k] , y = fa[y][k];
    return fa[x][0];
}
int main()
{
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    for(int i=1;i<=n;i++)
        lg[i] = lg[i-1] + (1<<lg[i-1] == i);
    dfs(s , 0);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}