【总结】lca最近公共祖先

一.定义：

给出有根树T中的两个不同的节点u和v，找到一个离根最远的节点x，使得x同时是u和v的祖先，x就是u和v的最近公共祖先(Lowest common ancestor)

二.暴力算法

先从u往根节点遍历，经过的点都打一个标记

再从v往根节点遍历，路上碰到的第一个打标记的点就是它们的LCA.

时间复杂度：一次询问是O(n)的，n为树的节点个数。

三.倍增算法

我们记fa[u]为u的父节点，即从u向根走1步能到达的节点，对根节点我们记fa[root] = 0.

记up[u] [k]为从u向根走2k步到达的节点。

显然有

up[u] [0] = fa[u]

up[u] [k] = up[up[u] [k – 1]] [k – 1]

具体实现

那么，有了up[u] [k]数组之后我们怎么求LCA呢？

若u和v的深度不同，则通过up数组先把他们调整到同一深度

我们从大到小枚举k，比较up[u] [k]与up[v] [k]

若up[u] [k] == up[v] [k]

说明up[u] [k]是u和v的公共祖先

若up[u] [k] != up[v] [k]

说明u和v还没有走过LCA

令u = up[u] [k], v = up[u] [k]

可以证明，最后u和v的父亲就是所求的LCA.

代码

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int read(){
    int f=0,a=0;char p=getchar();
    while(!isdigit(p)){f|=p=='-';p=getchar();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
    return f?-a:a; 
}
vector<int> m[500005];
int f[500005][21],dep[500005];
int tot;
int next[500005*2],first[500005*2],go[500005*2];
void firs(int u,int fa){
    dep[u]=dep[fa]+1;//该节点的深度 等于其父亲节点加一
    f[u][0]=fa;
    for(int i=0;i<=19;i++)f[u][i+1]=f[f[u][i]][i];
    for(int e=first[u];e;e=next[e]){
        int v=go[e];
        if(v==fa)continue;
        firs(v,u);
    }
}
inline int lca(int x,int y){//求x和y的最近公共祖先 
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[f[x][i]]>=dep[y])x=f[x][i];//让x和y到一个深度 
        if(x==y)return x;
    }
    for(int i=20;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    } 
    return f[x][0];
}
void Add(int u,int v){
     next[++tot]=first[u];first[u]=tot;go[tot]=v;
     next[++tot]=first[v];first[v]=tot;go[tot]=u;
}
int main(){
    int n,M,s;//n个节点 m个询问 s是根节点
    int x,y;
    n=read();M=read();s=read(); 
    for(int i=1;i<=n-1;i++){
        x=read();y=read();  
        Add(x,y);
    }  
    firs(s,0);
//  for(int i=1;i<=20;i++){
//      for(int j=1;j<=n;j++)cout<<f[j][i]<<" ";
//  }
    for(int i=1;i<=M;i++){
        x=read();y=read();
        cout<<lca(x,y)<<endl;
    }
    return 0;
}

至于例题的话写过一些了有时间再整理(趴。

【总结】lca最近公共祖先

原文：https://www.cnblogs.com/huixinxinw/p/12260355.html