Source Code
#include <bits/stdc++.h>

using namespace std;

const int N=2e5+5;

vector<int> adj[N];
int dp[N][20],hi[N],cl[N],co[N];
int n,q;

void dfs(int node,int pa)
{
	dp[node][0]=pa;
	for(int i=1;i<20;i++)
		dp[node][i]=dp[dp[node][i-1]][i-1];
	hi[node]=hi[pa]+1;
	cl[node]=cl[pa];
	if(adj[node].size()>=3)
		cl[node]=node;
	co[node]=co[pa]+(adj[node].size()>=3);
	for(int i:adj[node])
	{
		if(i==pa) continue;
		dfs(i,node);
	}
}

int lca(int x,int y)
{
	if(hi[x]<hi[y]) swap(x,y);
	for(int i=19;i>=0;i--)
	{
		if(hi[x]-(1<<i)>=hi[y])
			x=dp[x][i];
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--)
	{
		if(dp[x][i]!=dp[y][i])
		{
			x=dp[x][i]; y=dp[y][i];
		}
	}
	return dp[x][0];
}

int find(int x,int lc)
{
	int del=co[dp[lc][0]];
	for(int i=19;i>=0;i--)
	{
		if(hi[x]-(1<<i)<hi[lc]) continue;
		if(co[dp[x][i]]>del)
			x=dp[x][i];
	}
	return x;
}

int main()
{
	scanf("%d %d",&n,&q);
	for(int i=2;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		adj[x].push_back(i);
		adj[i].push_back(x);
	}
	dfs(1,0);
	while(q--)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		int lc=lca(x,y);
		int dis=hi[x]+hi[y]-2*hi[lc];
		if(adj[y].size()>1||x==y)
		{
			puts("yes");
			continue;
		}
		int best=-1;
		if(co[x]>co[dp[lc][0]])
			best=find(x,lc);
		if(hi[cl[y]]>=hi[lc]) best=cl[y];
		if(best==-1||best==x)
		{
			puts("no");
			continue;
		}
		int d=hi[x]+hi[best]-2*hi[lca(x,best)];
		if(d<=dis-d)
			puts("no");
		else
			puts("yes");
	}
}
Copy
Escape from TarkZoo mahmoudbadawy
GNU G++17
59 ms
21.9 MB
Accepted