洛谷 P3379 【模板】最近公共祖先（倍增LCA）

洛谷 P3379 【模板】最近公共祖先（倍增LCA）

题解：

一道LCA的模板题，用倍增LCA来做再合适不过了~时间复杂度为O(nlogn)
倍增的思想可以用在很多地方，这里就说说如何用倍增来解决LCA的问题吧~

自己画的图比较丑

假设我们要求的是节点u和v的LCA。旁边的数字表示节点的深度
首先，我们要先了解fa数组，数组fa[i][j]表示的是节点i的第2^j的祖先节点，比如fa[i][0]表示的就是i的父节点，那么我们就要先初始化这个数组，一次dfs就可以了，同时用数组depth[i]记录每个节点的深度。然后因为此时u和v不在同一深度，没有办法一起向上跳，那么我们就把深度较大的u先跳到和v相同的深度，也就是虚的圆框包含的那个点，此时，两者已经在同一深度了，可以同时向上跳，我们先让它们跳尽可能大的距离，此时它们的深度为4，于是就先往上跳2^2，也就是跳到根节点，此时它们相等了，但明显它们的LCA不是根节点，所以我们要找到第一次使u和v不同的点，也就是图中深度为3的两个点，此时u或者v的父节点就是它们的最近公共祖先。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#define MAX 500005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

struct edge{
    int to;
    int nxt;
}e[MAX*2];

int n,m,s,cnt=0;//n个节点，m次询问，s为根节点
int fa[MAX][20];//节点i的第2^j的祖先节点，最大不会超过2的20的次方
int head[MAX],depth[MAX];

void add(int a,int b){
    e[cnt].to=b;
    e[cnt].nxt=head[a];
    head[a]=cnt++;
}

void dfs(int u,int pre){//u为当前节点,pre当前节点的父节点
	int v;//v为与u相邻的节点
	for(int i=head[u];i!=-1;i=e[i].nxt){
		if(e[i].to!=pre){
			v=e[i].to;
			depth[v]=depth[u]+1;
			fa[v][0]=u;//v的父节点为u
			dfs(v,u);
		}
	}
}

int lca(int a,int b){
    if(depth[a]>depth[b]){//保证b的深度大于等于a的深度
        swap(a,b);
    }
    int t=depth[b]-depth[a];//t为两者的深度差
    while(t){//当它们不在同一深度，先让深度大的向上跳到同一深度
        int x=log2(t);
        b=fa[b][x];
        t=depth[b]-depth[a];
    }
    if(a!=b){//若它们没有跳到同一个点
        for(int i=log2(depth[a]);i>=0;i--){//同时向上跳，但不能跳到同一个点，因为可能跳得太多了
			if(fa[a][i]!=fa[b][i]){
				a=fa[a][i];
				b=fa[b][i];
			}
        }
		a=fa[a][0];//最后的结果等于a的父节点
    }
    return a;
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&n,&m,&s);
    int a,b;
    for(int i=0;i<n-1;i++){//前向星存边
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    dfs(s,0);
    for(int j=1;(1<<j)<=n;j++){//记录节点i的第2^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 = 2^(j-1) + 2^(j-1)
		}
    }
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);//读入a和b
        printf("%d\n",lca(a,b));//求a和b的最近公共祖先
    }
    return 0;
}