本题的 $nlog_n$ 解法： 虽然洛谷上已经被卡掉

先作树上倍增，对每个问题求解时先对两个点求lca，再把lca和剩下节点依次求lca 注意用记忆化搜索

冒昧地问一句为什么我成管理员了

#include <bits/stdc++.h>
using namespace std;
int n, m, logn, de[500005], f[500005][25], ans[500005];
vector<int> e[500005], pos[500005];
void dfs(int u)
{
    for (int &v : e[u])
        if (v != f[u][0])
        {
            de[v] = de[u]+1;
            pos[de[v]].push_back(v);
            dfs(v);
        }
}
int lca(int x, int y)
{
    if (de[x] < de[y])
        swap(x, y);
    for (int i = 0, p = de[x] - de[y]; p; i++, p >>= 1)
        if (p & 1)
            x = f[x][i];
    if (x == y)
        return x;
    for (int i = logn; i>=0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
int main()
{
    ios::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    logn = log2(n);
    for (int i = 1; i <= n; i++)
    {
        cin >> f[i][0];
        e[f[i][0]].push_back(i);
    }
    for (int i = 1; i <= logn; i++)
        for (int j = 1; j <= n; j++)
            f[j][i] = f[f[j][i-1]][i-1];
    de[1] = 1, pos[1].push_back(1);
    dfs(1);
    for (int i = 1; i <= m; i++)
    {
        int k, LCA;
        cin >> k;
        if (ans[k])
        {
            cout << ans[k] << endl;
            continue;
        }
        LCA = pos[k][0];
        for (int j = 1; j < (int)pos[k].size(); j++)
            LCA = lca(LCA, pos[k][j]);
        cout << LCA << endl;
        ans[k] = LCA;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=5000005;
int n,m,k,s,t,f[N],g[N],mx[N];
//f 子节点最大深度 g 子节点次大深度 mx 最大深度编号 
int ans[N],x,de[N],a[N];//a 以u为根的子树中的最大深度 
vector<int> e[N];
void dfs(int u){
	a[u]=de[u];
	for (int &v:e[u]){
		de[v]=de[u]+1;
		dfs(v);
		a[u]=max(a[u],a[v]);
		if (f[u]<a[v]){
			g[u]=f[u];f[u]=a[v];mx[u]=v;
		}
		else if (g[u]<a[v]) g[u]=a[v];
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for (int i=1;i<=n;++i){
		cin>>s;
		if (s) e[s].push_back(i);
	}
	de[1]=1;
	dfs(1);
	ans[1]=1;
	for (int i=2;i<=f[1];++i){
		int now=ans[i-1];
		while (de[now]<i && f[now]>=i && g[now]<i) 
			now=mx[now];
		ans[i]=now;
	}
	for (int i=1;i<=m;++i) cin>>x,cout<<ans[x]<<"\n";
}