定义
LCA，最近公共祖先，是指一棵树上两个节点的深度最大的公共祖先。也可以理解为两个节点之间的路径上深度最小的点。
我们这里用了倍增的方法求了LCA。
我们的基本的思路就是，用dfs遍历求出所有点的深度。f[i][j]数组用来求的是距离节点i，距离2^j的祖先。可以知道，f[i][0]就是它的直接父亲。然后通过倍增的思路求出father数组的所有元素。然后进行lca。求lca的基本思路是：先让深度较大的点向上跳，
然后x和y再同时向上跳2的幂，总会跳到这样两个点，他们的父亲结点是同一个点，那就是x和y的LCA。
首先我们需要用邻接表建一颗参天大树~
重头戏——倍增。
int dep[maxn],f[maxn][];
/*dep数组用来记录当前点的深度
f[i][j]代表距离i 2^j的祖先
*/
深度和直接父亲：
void pre(int u,int fa)
{
dep[u]=dep[fa]+; //更新深度
f[u][]=fa;//更新父亲结点
for(int i=;(<<i)<=dep[u];i++){//预处理出f数组
f[u][i]=f[f[u][i-]][i-]; //这个转移可以说是算法的核心之一
//u的2^(i-1)级祖先的2^(i-1)级祖先就是u的2^i级祖先。
}
for(int i=head[u];i;i=e[i].next){//遍历邻接表
int to=e[i].to;
if(to==f[u][]) continue;//如果to是u的父亲，那么就说明这条边被访问过了，不能再回溯了
pre(to,u);//继续深度优先遍历
}
}
有的预处理工作都完成了。我们开始求LCA~
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);//让x的深度更深
int cha=dep[x]-dep[y];//cha是x和y的深度之差
for(int i=;(<<i)<=cha;i++){
if((<<i)&cha){
x=f[x][i];
}
}//让x跳到跟y相同高度上
if(x!=y){//如果a和b不是同一个结点那么就要继续跳,如果是同一个结点，那么它就是LCA
for(int i=(int)log2(n);i>=;i--){//从大到小跳。正确性显然。
if(f[x][i]!=f[y][i]){//如果不相等，就说明该节点的深度还是比LCA大
x=f[x][i];
y=f[y][i];
//那就继续跳
}
}
x=f[x][];
//这个时候x和y还不是同一个节点，但是x和y的父亲就是x和y的lca。
}
return x;
}
常数优化：另外预处理出lg避免重复调用log函数
for(int i=;i<=n;i++)
lg[i]=lg[i-]+(<<lg[i-]==i);
P3379 【模板】最近公共祖先（LCA）
给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
对于100%的数据：N<=500000，M<=500000
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define num ch-'0'
#define rep(i,k,n) for(int i=k;i<=n;++i)
using namespace std;
int n,m,s,cnt=;
int head[],dep[],fa[][],lg[];
inline void get(int &res)
{
char ch;bool flag=;
while(!isdigit(ch=getchar()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getchar());res=res*+num);
(flag)&&(res=-res);
}
struct node
{
int to,nex;
}e[];
inline void add(int x,int y)
{
e[++cnt].nex=head[x];
e[cnt].to=y;
head[x]=cnt;
}
void init(int u,int f)
{
dep[u]=dep[f]+;
fa[u][]=f;
for(int i=;(<<i)<=dep[u];++i)
fa[u][i]=fa[fa[u][i-]][i-];
for(int i=head[u];i;i=e[i].nex)
{
if(e[i].to==f) continue;
init(e[i].to,u);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y])
x=fa[x][lg[dep[x]-dep[y]]-];
if(x!=y)
{
for(int i=lg[dep[x]];i>=;--i)
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
x=fa[x][];
}
return x;
}
int main()
{
get(n),get(m),get(s);
rep(i,,n-)
{
int x,y;
get(x),get(y);
add(x,y);add(y,x);
}
init(s,);
rep(i,,n) lg[i]=lg[i-]+(<<lg[i-]==i);
rep(i,,m)
{
int x,y;
get(x),get(y);
printf("%d\n",lca(x,y));
}
return ;
}
参考https://blog.csdn.net/qq_42386465/article/details/82978520