最近公共祖先注意有根树

向上标记法

1.先判断u，v是否是同一个节点，若是，那最近总共祖先就是它本身

2.先对u，先来标记，再去向上走，u只管标记

3.一种是v本身是u祖先，另一种v向上走遇到了标记的，一遇到就返回就是了

4.最后没找到

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int p[N],st[N];
//向上标记法
int LCA(int u,int v)
{
    if(u==v)return u;
    st[u]=1;//标记
    //x=p[x],则x是祖先
    while(p[u]!=u)
    {
        u=p[u];//代入父节点，向上走
        st[u]=1;//标记
    }
    if(st[v])return v;//v是u的祖先
    while(p[v]!=v)//v也向上走
    {
        v=p[v];
        if(st[v])return v;//走到共同点了
    }
    return 0;//没有最近公共祖先
}
int main()
{




    return 0;
}


void bfs(int rt)
{
    queue<int>q;
    memset(dep,0x3f,sizeof dep);
    dep[0]=0;//哨兵深度为0
    dep[rt]=1;//根节点为1
    q.push(rt);//根节点入队
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(auto &w:g[t])
        {
            if(dep[w]>dep[t]+1)//说明这个出点还未被搜索过
            {
                dep[w]=dep[t]+1;
                //先入队
                q.push(w);
                f[w][0]=t;//从w这个出点开始跳，跳2的0次方，跳到t
                for(int k=1;k<=15;k++)
                {
                    f[w][k]=f[f[w][k-1]][k-1];
                }
            }
        }
    }

}

树上倍增法

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int>g[N];
int f[N][16],dep[N],rt;
int n,m;
void bfs(int rt)
{
    queue<int>q;
    memset(dep,0x3f,sizeof dep);
    dep[0]=0;//哨兵深度为0
    dep[rt]=1;//根节点为1
    q.push(rt);//根节点入队
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(auto &w:g[t])
        {
            if(dep[w]>dep[t]+1)//说明这个出点还未被搜索过
            {
                dep[w]=dep[t]+1;
                //先入队
                q.push(w);
                f[w][0]=t;//从w这个出点开始跳，跳2的0次方，跳到t
                //递推预处理
                for(int k=1;k<=15;k++)
                {
                    f[w][k]=f[f[w][k-1]][k-1];
                }
            }
        }
    }   
}
int lca(int a,int b)
{
    //这里细心，这里要a在b的下面，那a的深度应该大于b
    if(dep[a]<dep[b])swap(a,b);
    for(int k=15;k>=0;k--)
    {
        if(dep[f[a][k]]>=dep[b])
        a=f[a][k];
    }
    if(a==b)return a;
    for(int k=15;k>=0;k--)
    {
        if(f[a][k]!=f[b][k])
        {
            a=f[a][k];
            b=f[b][k];
        }
    }
    return f[a][0];//最终答案即为a或者b的父节点，因为向上跳一步就是父节点
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(b==-1)rt=a;
        else 
        {
            g[a].push_back(b);
            g[b].push_back(a);
        }
    }
    //预处理祖宗节点
    bfs(rt);//从根节点开始搜
    scanf("%d",&m);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int p=lca(a,b);
        if(p==a)puts("1");
        else if(p==b)puts("2");
        else puts("0");
    }
    return 0;
}

例题

最近公共祖先

代码

注意倍增数组根据题意来开大小

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int>g[N];
int n,m,s;
int d[N],f[N][26];
void bfs(int rt)
{
    memset(d,0x3f,sizeof d);
    d[0]=0;
    d[rt]=1;
    queue<int>q;
    q.push(rt);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(auto &w:g[t])
        {
            if(d[w]>d[t]+1)
            {
                d[w]=d[t]+1;
                q.push(w);
                f[w][0]=t;//0
                for(int k=1;k<=25;k++)//[1,15]
                f[w][k]=f[f[w][k-1]][k-1];
            }
        }
    }
}
int lca(int a,int b)
{
    if(d[a]<d[b])swap(a,b);
    for(int k=25;k>=0;k--)
    {
        if(d[f[a][k]]>=d[b])
        a=f[a][k];
    }
    if(a==b)return a;
    for(int k=25;k>=0;k--)
    {
        if(f[a][k]!=f[b][k])
        {
            a=f[a][k];
            b=f[b][k];
        }
    }
    return f[a][0];
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    int p=n-1;
    while(p--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bfs(s);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }

    return 0;
}