最近公共祖先（LCA）笔记
【模板】最近公共祖先（LCA）
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 \(N,M,S\)，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 \(N-1\) 行每行包含两个正整数 \(x, y\)，表示 \(x\) 结点和 \(y\) 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 \(M\) 行每行包含两个正整数 \(a, b\)，表示询问 \(a\) 结点和 \(b\) 结点的最近公共祖先。
输出格式
输出包含 \(M\) 行，每行包含一个正整数，依次为每一个询问的结果。
样例 #1
样例输入 #1
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
样例输出 #1
4
4
1
4
4
提示
对于 \(30\%\) 的数据，\(N\leq 10\)，\(M\leq 10\)。
对于 \(70\%\) 的数据，\(N\leq 10000\)，\(M\leq 10000\)。
对于 \(100\%\) 的数据，\(1 \leq N,M\leq 500000\)，\(1 \leq x, y,a ,b \leq N\)，不保证 \(a \neq b\)。
样例说明：
该树结构如下：
第一次询问：\(2, 4\) 的最近公共祖先，故为 \(4\)。
第二次询问：\(3, 2\) 的最近公共祖先，故为 \(4\)。
第三次询问：\(3, 5\) 的最近公共祖先，故为 \(1\)。
第四次询问：\(1, 2\) 的最近公共祖先，故为 \(4\)。
第五次询问：\(4, 5\) 的最近公共祖先，故为 \(4\)。
故输出依次为 \(4, 4, 1, 4, 4\)。
2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。
大致思路
就原本是两个点一步一步往上跳直到跳到同一点上。优化的方法是根据两个节点的的深度，如不同，向上调整深度大的节点，使得两个节点在同一层上，如果正好是祖先，结束；否则，将两个节点同时上移，查询最近公共祖先(两个过程均使用倍增加速)。
code
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,rt;
vector<int>g[N];
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
int f[N][21];//f[i][j] 结点i往上跳2^j步的祖先结点
//f[i][j]=f[f[i][j-1]][j-1]
int d[N];//d[i] 结点i处于第几层
void dfs(int u,int fa)
{
f[u][0]=fa;
for(int i=0;i<(int)g[u].size();i++)
{
int v=g[u][i];
if(v==fa) continue;
d[v]=d[u]+1;
dfs(v,u);
}
}
int get_lca(int x,int y)
{
//d[x]>d[y]
if(d[x]<d[y]) swap(x,y);
int cha=d[x]-d[y];
for(int i=20;i>=0;i--)
if(cha>>i&1) 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];
}
int main()
{
n=read();m=read();rt=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
g[x].push_back(y);g[y].push_back(x);
}
d[rt]=1;
dfs(rt,rt);
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
while(m--)
{
int x=read(),y=read();
printf("%d\n",get_lca(x,y));
}
return 0;
}