没什么好说的，倍增优化即可

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int fa[N][20],dep[N],n,q;
vector<int>G[N];
void dfs(int x,int xfa){
	fa[x][0]=xfa;dep[x]=dep[xfa]+1;
	for(int i=1;i<=19;i++)fa[x][i]=fa[fa[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=19;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	if(x==y)return x;
	for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=2;i<=n;i++){
		int x;scanf("%d",&x);x++;
		G[i].push_back(x);
		G[x].push_back(i); 
	}
	dep[0]=0;dfs(1,0);
	while(q--){
		int x,y;scanf("%d%d",&x,&y);x++;y++;
		printf("%d\n",Lca(x,y)-1);
	}
	return 0;
}

重链版：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
vector<int> G[N];
int fa[N]/*节点父亲*/, dep[N]/*节点深度*/, siz[N]/*以i为根子树大小*/,
son[N]/*i的重儿子，即子树最大的儿子*/, top[N]/*i所在重链的顶端*/;

void dfs1(int x, int xfa)/*处理出每个节点的重儿子*/
{
    fa[x] = xfa;/*记录父亲*/ dep[x] = dep[xfa] + 1/*记录深度*/;
    siz[x] = 1/*x节点自己*/; son[x] = -1/*还没找重儿子*/;
    for (int y : G[x]/*遍历儿子*/) if (y != xfa)
    {
        dfs1(y, x);/*递归处理*/
        siz[x] += siz[y];/*统计儿子y的子树大小*/
        if (son[x] == -1/*还没重儿子*/ or siz[son[x]] < siz[y]/*y子树比原来重儿子子树更大*/)
            son[x] = y;/*更新x的重儿子*/
    }
}

void dfs2(int x, int tp)/*处理每个点属于哪条重链*/
{
    top[x] = tp;/*x所处重链顶端为tp*/
    if (son[x] > 0/*如果*/) dfs2(son[x], tp)/*x的重儿子延续重链*/;
    for (int y : G[x]) /*处理x的其他儿子*/if (y != fa[x] and y != son[x])
        dfs2(y, y);/*y以自己为顶端形成一条新重链*/
}

int LCA(int x, int y)/*找x与y的LCA*/
{
    for (; top[x] != top[y]; x = fa[top[x]])/*只要两点不在同一重链内, 更低的点就跳到重链顶端再往上一个节点*/
        if (dep[top[x]] < dep[top[y]]) swap(x, y);/*维护x为更低的点, 就始终只用跳x*/
    return dep[x] < dep[y] ? x : y;/*当x与y在同一重链内,说明其中一点为另一点祖先, 返回较浅的点*/
}

int main()
{
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 1, x; i <= n - 1; i++)
    {
        scanf("%d", &x); x ++;/*题目要求0节点为根, 节点编号均加1*/
        G[x].push_back(i + 1);
        G[i + 1].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1, x, y; i <= m; i++)
    {
        scanf("%d %d", &x, &y); x++, y++;
        printf("%d\n", LCA(x, y) - 1);
    }
    return 0;
}

st表版：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
vector<int> G[N];
int D/*最大能跳多远, 即为2^D步*/, dep[N]/*节点深度*/, st[N][20]/*st[x][i]:节点x往上跳2^i步*/;

void dfs(int x, int xfa)/*处理每个点跳跃达到的点, 即st[x][i]*/
{
	dep[x] = dep[xfa] + 1;/*记录深度*/
	st[x][0] = xfa;/*x往上跳1步就是x的父亲*/
    for (int i = 1; i <= D; i++)
        st[x][i] = st[st[x][i-1]][i-1];/*x跳2^i步, 等于x先跳2^(i-1)步, 再跳2^(i-1)步*/
	for (int y : G[x]) if (y != xfa)
		dfs(y, x);/*递归x的儿子*/
}

int LCA(int x, int y)/*找x与y的LCA*/
{
	if (dep[x] < dep[y]) swap(x, y);/*交换x和y, 令x为更低的点*/
	for (int i = D; i >= 0; i--)
    {
        if (dep[st[x][i]] >= dep[y]) x = st[x][i];
        /*x不断向上跳跃，直到x和y在同一深度*/
        /*从最大跳跃距离(2^D步)开始跳跃, 每次距离减半，如果不会超过目标深度就进行跳跃*/
        /*x和y的距离差一定可以拆分为若干个2^i步相加*/
    }
    if (x == y) return x; /*如果x和y是同一点则直接返回答案*/
	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()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
    for (int i = 1, x; i <= n - 1; i++)
    {
        cin >> x; x ++;/*题目要求0节点为根, 节点编号均加1*/
        G[x].push_back(i + 1);
        G[i + 1].push_back(x);
    }
	D = log2(n);/*处理一次最多可以跳几步*/
	dfs(1, 0);/*处理每个点跳跃达到的点, 即st[x][i]*/
	for (int i = 1, x, y; i <= m; i++)
	{
		cin >> x >> y; x ++; y ++;
		cout << LCA(x, y) - 1 << '\n';
	}
	return 0;
}

tarjan版（虽然快但只能离线，不推荐）：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int fa[N];
int findfa(int x){return fa[x]==x?fa[x]:fa[x]=findfa(fa[x]);}
vector<int>G[N];vector<pair<int,int>>e[N];
int v[N],ans[N];
void tarjan(int x)
{
	v[x]=1;
	for(int y:G[x])if(!v[y])
	{
		tarjan(y);
		fa[y]=x;
	}
	for(auto i:e[x])
	{
		int y=i.first,id=i.second;
		ans[id]=findfa(y);
	}
}
int main()
{
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=2;i<=n;i++)
	{
		int x;cin>>x;x++;
		G[x].push_back(i);
		G[i].push_back(x);
	}
	for(int i=1;i<=q;i++)
	{
		int x,y;cin>>x>>y;x++,y++;
		e[x].push_back({y,i});
		e[y].push_back({x,i});
	}
	tarjan(1);
	for(int i=1;i<=q;i++)cout<<ans[i]-1<<'\n';
	return 0;
}

重链版：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int>G[N];
int dep[N],fa[N],son[N],siz[N],top[N],dfn[N],_dfn[N],tsp;
void dfs1(int x,int f)
{
	dep[x]=dep[f]+1;fa[x]=f;siz[x]=1;int mx=0;
	for(int y:G[x])if(y!=f)
	{
		dfs1(y,x);
		siz[x]+=siz[y];
		if(mx<siz[y])mx=siz[y],son[x]=y;
	}
}
void dfs2(int x,int tp)
{
	top[x]=tp;dfn[x]=++tsp;_dfn[tsp]=x;
	if(son[x])dfs2(son[x],tp);
	for(int y:G[x])if(y!=fa[x]&&y!=son[x])dfs2(y,y);
}
int lca(int x,int y)
{
	for(;top[x]!=top[y];x=fa[top[x]])if(dep[top[x]]<dep[top[y]])swap(x,y);
	return dep[x]<dep[y]?x:y;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,q;cin>>n>>q;
	for(int i=2;i<=n;i++)
	{
		int x;cin>>x;x++;
		G[x].push_back(i);
	}
	dfs1(1,0);dfs2(1,1);
	while(q--)
	{
		int x,y;cin>>x>>y;x++,y++;
		cout<<lca(x,y)-1<<'\n';
	}
	return 0;
}

st表版：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int>G[N];
int dep[N],st[N][20],D; 
void dfs(int x,int f)
{
	dep[x]=dep[f]+1;
	st[x][0]=f;for(int i=1;i<=D;i++)st[x][i]=st[st[x][i-1]][i-1];
	for(int y:G[x])if(y!=f)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,q;cin>>n>>q;
	for(int i=2;i<=n;i++)
	{
		int x;cin>>x;x++;
		G[x].push_back(i);
	}
	D=log2(n);dfs(1,0);
	while(q--)
	{
		int x,y;cin>>x>>y;x++,y++;
		cout<<lca(x,y)-1<<'\n';
	} 
	return 0;
}