题解 P3379 【【模板】最近公共祖先（LCA）】
liusu201601 · · 题解
应用概括：
lca主要解决树上面的两点之间的关系问题，核心是倍增数组的应用，注意根的f数组的初始化：
操作步骤：
1、确定根，让根的层数为1，定义f[r][0]作为边界，往上跳就出界了：
d[r]=1;
f[r][0]=0 ；2、构树：主要是把点都打上分层，跑dfs(x)，让本来凌乱的图，变成一棵树，下面用 d[y] 表示 y 号点的层数,f[y][0]表示y点往上跳第一步的时候，必然是自己父亲：
d[y]=d[x]+1；
f[y][0]=x ；3、通过两层循环，把倍增数组构造出来：
第一层循环是步数，从小到大；
第二层循环是点数，
//=================================
这是本次题解最难最难最难的东东！！
原理类似：合并石子：dp的经典思路,先把小规模的状态都算出来，再层层推出大规模的数据。
//=================================
4、lca函数 就是一个简单的查询操作：
x、y分别是树上的两个点，找他们的最近的公共祖先
开头用一个判断，规定 x 的深度一定比 y 大，否则就用 swap函数 交换一下。
第一个循环是：让 x 往上跳，去找 ‘y的所在层’
如果 x 和 y 重合了，就已经是答案了；
否则 让 x 和 y 一起向上跳，跳到 ‘拥有共同父亲的下一层’
轻轻地输出这位父亲，完成~~~
下面是代码与注解：
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500005;
int n,m,r,len=0;
int d[maxn],f[maxn][30],h[maxn];// d数组：分层用，f数组：倍增跳跃， h数组：邻接表；
struct nod{int x,y,gg;}b[maxn*2];//存边：双向边，所以数据要开够
void ins(int x,int y)//邻接表
{
len++; b[len].x=x; b[len].y=y; b[len].gg=h[x]; h[x]=len;
}
void dfs(int x) //x 去找所有的 y
{
for(int i=h[x];i>0;i=b[i].gg)
{
int y=b[i].y;
if(d[y]==0) // y 未被访问过
{
d[y]=d[x]+1;// y 是x的儿子，所以层数+1
f[y][0]=x; // y向上跳一格，一定是到 x
dfs(y);
}
}
}
int lca(int x,int y) //查找 x 与 y 的最近公共祖先
{
if(d[x]<d[y]) swap(x,y);// 要求 x 比较深， 去找 y
for(int i=20;i>=0;i--) //先让 x 跳到 y 的同层
{
if(d[f[x][i]]>=d[y])
{
x=f[x][i];
}
}
if(x==y) return x; //如果重合，就已经结束了
for(int i=20;i>=0;i--)//不重合，x 和 y 一起往上跳
{
if(f[x][i]!=f[y][i]) //只要父亲不同，就跳，父亲相同，就停了
{ // 最后一次，是没有跳上去的
x=f[x][i]; y=f[y][i];
}
}
return f[x][0];//要输出，必须要跳最后一次
}
int main()
{
scanf("%d %d %d",&n,&m,&r);
for(int i=1;i<=n;i++) { h[i]=d[i]=0; }
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y); ins(x,y);ins(y,x);//双向边
}
d[r]=1;f[r][0]=0;// 以 r 为根
dfs(r);//构树：分层+倍增的 0
for(int i=1;i<=20;i++)//倍增数组的建立 ：请类比 合并石子 搞清楚
{ // 这里是整个算法的核心
for(x=1;x<=n;x++) //这里是整个算法的核心
{ //这里是整个算法的核心
f[x][i]=f[f[x][i-1]][i-1];//这里是整个算法的核心
}
}
for(int i=1;i<=m;i++)//询问
{
scanf("%d %d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
```