LCA

· · 个人记录

LCA(最近公共祖先)

【模板】最近公共祖先（LCA）

​最近公共祖先_百度百科

定义

在有根树上，两点的祖先有公共部分，这些点叫做他们的公共祖先，而其中深度最深的点，叫作它们的最近公共祖先（​LCA⁡，Lowest Common Ancestors）。

求解

暴力

先自上到下将a节点的所有祖先打一个标记，再自下至上找第一个打了标记的点，即为二者的LCA

倍增

在用st表处理区间最值查询时，我们用到了倍增的思想，那么在求解LCA时，是否可以也用倍增呢？答案是可以的。 定义fa_{i,j}是i的2^j个祖先（可用递推），dep_i表示i节点的深度（dfs） 由于一个整数一定能化作二进制，那么我们每次向上跳到a节点的2的若干次方祖先处，一定能跳到a,b,的LCA处 对于b同理 那么可以先将a,b跳到同一深度处，再让两个点同时向上跳，直到两个点的父亲相同

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=5e5+10;
int n,m,s; 
vector<int > G[N];
int dep[N];
int fa[N][21];
void dfs(int u,int _fa)//求深度 
{
    fa[u][0]=_fa;
    dep[u]=dep[_fa]+1;
    for(auto v:G[u])
    {
        if(v==_fa)
        {
            continue;
        }
        dfs(v,u);
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])//便于操作 
    {
        swap(x,y);
    }
    for(int i=20;i>=0;i--)//从大到小枚举,能跳就跳,因此不会出现越界或没跳到的情况,后面同理 
    {
        if(dep[fa[x][i]]>=dep[y])
        {
            x=fa[x][i];
        }
    }
    if(x==y)//如果跳到同一个点上,则这个点为LCA 
    {
        return x;
    }
    for(int i=20;i>=0;i--)//一起跳 
    {
        if(fa[x][i]!=fa[y][i])//当二者的同辈祖先不一致时,向上跳 
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];//由于fa[x][0]中放的是父亲, 因此要返回二者的父亲 
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(false);//加快读入 
    cin>>n>>m>>s;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);//存树 
    }
    dfs(s,0);
    for(int j=1;j<=20;j++)
    {
        for(int i=1;i<=n;i++)
        {
            fa[i][j]=fa[fa[i][j-1]][j-1]; //递推  i的2^j次祖先即为i的2^(j-1)祖先的2^(j-1)次祖先(2^(j-1)+2^(j-1)=2^j) 
        }
    }
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
    return 0;
}

欧拉序

欧拉序

类似于dfs序，我们每访问到这个点（包括回溯），就在序列后加上这一项 由于我们每一个孩子回溯时，都会访问一次父亲，因此，欧拉序的长度是n+n−1=2n−1

与LCA

当我们dfs访问到a,b,的LCA时，继续遍历，一定会遍历到a,b且a,b不在同一子树上（反证法，如果在，这个点就不是LCA了） 所以，a,b(第一次出现在欧拉序中)之间的欧拉序一定会回溯到LCA,且LCA一定为其中深度最小的点 因此先求出全树的欧拉序，然后用st表储存2的若干次方内深度最小的点，每次询问时，查询a,b之间的深度最小的点

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=5e5+10;
vector<int> G[N];
int n,m,s;
int f[2*N][22];
int oula[2*N];
int cnt;
int dep[N];
int vis[2*N];
void dfs(int u,int fa)//处理深度和欧拉序 
{
    cnt++;
    dep[u]=dep[fa]+1;
    oula[cnt]=u;
    vis[u]=cnt;//记录第一次出现的欧拉序的下标 
    for(auto v:G[u])
    {
        if(v==fa)
        {
            continue;
        }
        dfs(v,u);
        cnt++;
        oula[cnt]=u;
    }
}
void build()//处理st表 
{
    for(int i=1; i<=cnt; i++)
    {
        f[i][0]=oula[i];
    }
    for(int j=1; j<=20; j++)
    {
        for(int i=1; i+(1<<j)<=cnt; i++)
        {
            int t1=f[i][j-1];
            int t2=f[i+(1<<(j-1))][j-1];
            if(dep[t1]<dep[t2])
            {
                f[i][j]=t1;
            }
            else
            {
                f[i][j]=t2;
            }
        }
    }
}
int st(int l,int r)//查询l,r之间的深度最小的点 
{
    int p=log2(r-l+1);
    if(dep[f[l][p]]>dep[f[r-(1<<p)+1][p]])
    {
        return f[r-(1<<p)+1][p];
    }
    else
    {
        return f[l][p];
    }
}
int lca(int l,int r)//求LCA 
{
    if(vis[l]>vis[r])
    {
        swap(l,r);
    }
    l=vis[l];
    r=vis[r];
    return st(l,r);
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>m>>s;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(s,0);
    build();
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
    return 0;
}