其实求 LCA 还有一个方法，就是转化为欧拉序列上的 RMQ 问题

听起来挺复杂，其实很简单，拿样例来举例：

9 6 
1 
1 
2 
8 
1 
8 
6 
6  

把图画好，然后用dfs过一遍，经过的点的顺序（欧拉序）就是：

1 2 4 2 1 3 1 6 8 5 8 7 8 6 9 6 1

同时处理出每一个点的深度：

1 2 1 2 1 2 1 2 3 4 3 4 3 2 3 2 1

对与每一个询问，比如9 5，找到他们在欧拉序里面的位置，两个位置之间深度最浅的一个点必然是这两个点的 LCA 。

对于找深度最浅的点，一般都要用数据结构进行维护，但显然这道题暴力乱搞就行了。用数据结构优化的代码可以自行思考。

喜闻乐见的代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
	int to,next;
} edge[2001];
int n,m,cnt,head[1001],dep[1001];
vector<int> dfn;
void dfs(int x)//求欧拉序和深度
{
	dfn.push_back(x);
	for(int i=head[x];i;i=edge[i].next)
	{
		dep[edge[i].to]=dep[x]+1;
		dfs(edge[i].to);
		dfn.push_back(x);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		edge[i].to=i+1;
		edge[i].next=head[x];
		head[x]=i;
	}
	dfs(1);
	while(m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int s,t;
		for(int i=0;i<dfn.size();i++)
			if(dfn[i]==x)
			{
				s=i;
				break;
			}
		for(int i=0;i<dfn.size();i++)
			if(dfn[i]==y)
			{
				t=i;
				break;
			}
		if(s>t)
			swap(s,t);
		int ans,minn=1e9;
		for(int i=s;i<=t;i++)
			if(dep[dfn[i]]<minn)
			{
				minn=dep[dfn[i]];
				ans=dfn[i];
			}
		cout<<ans<<endl;
	}
}

P3019

题意简述

• 给你一棵树中每个结点（除根）的父结点。
• $m$ 次询问，每次询问两结点的最近共同祖先（LCA）。

LCA 的定义

LCA 即最近共同祖先，我们要先清楚它的定义。

题目中是这么说的：

两个结点的路径上离根结点最近的结点。

也可以这么定义：

两个结点共同的祖先结点中，离这两个结点最近的结点。

那么这道题就是 LCA 了。

暴力

很容易想到的步骤：

1. dfs 求出每个点的深度。
2. 将更深的点向上一步步走到和另一个点一样深的地方。
3. 两个点一起向上走，直到祖先。

复杂度 $O(nm)$，好像可以，但是板子题过不去，所以要优化。

倍增 LCA

倍增思想在 ST 表中也用到了。如果你会 ST 表，这个应该不是问题。

既然大部分时间都用在了向上爬的过程，那预处理出每个结点的所有祖先结点不就行了？然而预处理太慢，还会爆空间，所以放弃。

解决方法是只保存部分祖先，即 $2^x(x\ge0)$ 级祖先。也就是说，一次只能爬 $2^x$ 层。

定义 $f(i,j)$ 表示 $i$ 的 $2^j$ 级祖先。定义父结点为 $1$ 级祖先。

我知道你觉得这么做很别扭，看看哪里有问题：

预处理

如何快速求出 $f(i,j)$ 呢？

容易得到递推式：$f(i,j)=f(f(i,j-1),j-1)$。

意思是说，$i$ 的 $4$ 级祖先就是 $i$ 的 $2$ 级祖先的 $2$ 级祖先。

有点像 dp？没错，从小到大枚举 $j$，就能快速算出。

向上爬

不能一步步向上爬了，那该怎么爬？

刚才说过：一次只能爬 $2^x$ 层。

那比如要爬 $10$ 层，就可以先爬 $2$ 层，再爬 $8$ 层。

但问题是我们不知道要爬几层啊。

从大往小

先尝试爬 $2^{10}$ 层，发现不行；

再尝试爬 $2^9$ 层，还是不行；

……

再尝试爬 $2^3$ 层，发现可以。

再尝试爬 $2^2$ 层，还是不行。

再尝试爬 $2^1$ 层，又可以了。

再尝试爬 $2^0$ 层，还是不行。

结束。

遗憾的是，我们甚至不能快速判断这个点是不是 LCA，也叫不能快速判断能否向上爬 $2^x$。但是可以判断它们的 $2^x$ 级祖先是否相同，如果相同，无论是不是 LCA，一律禁止爬；如果不同，就可以。这样显然无法到达 LCA，但是可以到 LCA 的子节点。

代码

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,fa[1010][20],deep[1010];
//fa[i][j] 即上文的 f(i,j)，deep 即深度
vector<int>son[1010];//每个点的所有子结点
void dfs(int x){//用来标记深度
	for(int i=0;i<son[x].size();i++){
		deep[son[x][i]]=deep[x]+1;//标记深度
		dfs(son[x][i]);//继续搜索
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++){
		int x;
		scanf("%d",&x);
		fa[i][0]=x;//父结点为2^0 级祖先
		son[x].push_back(i);
	}
	for(int i=1;i<20;i++)
		for(int j=1;j<=n;j++)
			fa[j][i]=fa[fa[j][i-1]][i-1];//倍增递推
	deep[1]=1;//根节点的深度为 1
	dfs(1);//标记深度
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(deep[x]>deep[y])
			swap(x,y);//这样 y 一定比 x 深
		for(int i=19;deep[x]<deep[y];i--)//从大到小枚举
			if(deep[fa[y][i]]>=deep[x])//深度不能比 x 小
				y=fa[y][i];//向上爬
		if(x==y){//这时下面的方法会错
			printf("%d\n",x);
			continue;
		}
		for(int i=19;x!=y&&i>=0;i--)
			if(fa[x][i]!=fa[y][i]){//不能相等
				x=fa[x][i];
				y=fa[y][i];
			}
		printf("%d\n",fa[x][0]);//这时 x 和 y 都是 LCA 的子结点
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
vector<int>G[N]; 
int D,dep[N],st[N][20];
void dfs(int x,int xfa)
{
    dep[x]=dep[xfa]+1;
    st[x][0]=xfa;for(int i=1;i<=D;i++)st[x][i]=st[ st[x][i-1] ][i-1];
    for(int y:G[x])if(y!=xfa)
        dfs(y,x);
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y); 
    for(int i=D;i>=0;i--)if(dep[st[x][i]]>=dep[y] )x=st[x][i];
    if(x==y) return x;
	for(int i=D;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
    return st[x][0];
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=2,x;i<=n;i++)
    {
        scanf("%d",&x);
        G[x].push_back(i);
    }
    D=log2(n);memset(dep,0,sizeof(dep));memset(st,0,sizeof(st));
    dfs(1,0);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
}