LCA
LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。
——百度百科
【模板】
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式：
第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
输出格式：
输出包含M行，每行包含一个正整数，依次为每一个询问的结果。
数据规模：
对于100%的数据：N<=500000，M<=500000
倍增算法：
#include<cstdio>
#include<iostream> //swap
#define MAXN 500010
using namespace std;
int n,m,s,tot;
int depth[MAXN],fa[MAXN][22],log2[MAXN],head[MAXN];
struct ss
{
int next,to;
}way[MAXN<<1];
void add(int x,int y)
{
way[++tot].next=head[x]; //next边记录点(x)的第(++tot)出边，head其点为最后一条边
way[tot].to=y; //to记录出边指向的点
head[x]=tot;
}
void dfs(int f,int fath)
{
depth[f]=depth[fath]+1;
fa[f][0]=fath;
for(int i=1;(1<<i)<=depth[f];i++)
fa[f][i]=fa[fa[f][i-1]][i-1]; //f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先
for(int i=head[f];i;i=way[i].next)
if(way[i].to!=fath) dfs(way[i].to,f); //遍历除爸爸外所有的儿砸
}
int lca(int x,int y)
{
if(depth[x]<depth[y]) swap(x,y); //设x的深度 >= y的深度
while(depth[x]>depth[y])
x=fa[x][log2[depth[x]-depth[y]]-1]; //由于之前推log2多1
if(x==y) return x; // 如果y是x的祖先，那他们的LCA肯定就是y
for(int k=log2[depth[x]]-1;k>=0;k--) //不断向上跳
if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k]; //跳到它们LCA的下面一层，如果不相等就跳过去
return fa[x][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int x,y,i=1;i<=n-1;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(s,0);
for(int i=1;i<=n;i++)
log2[i]=log2[i/2]+1; //i/2自动整型（log2[i]=log2[i-1]+(1<<log2[i-1]==i)；这样写更高大上）
for(int x,y,i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
原文：https://www.cnblogs.com/RR-Jin/p/11038071.html