Source Code
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
// please, read the question correctly (do you need set or multiset)???
const int N=200010; //check the limits, dummy
vector<int> a[N];
int n, m;

int pa[N][20];
int dp[N];
void dfs(int x){
	if(dp[x])return;
	dfs(pa[x][0]);dp[x]=dp[pa[x][0]]+1;
}
void pre(){
	for(int j=1; j<20; ++j){
		for(int i=1; i<=n; ++i){
			pa[i][j] = pa[pa[i][j-1]][j-1];
		}
	}
}
int lca(int x, int y){
	if(dp[x]<dp[y]){
		swap(x,y);
	}
	int tmp1 = dp[x]-dp[y];
	for(int i=0; i<20; ++i){
		if((1<<i)&tmp1)x=pa[x][i];
	}
	if(x==y)return x;
	for(int i=19; i>=0; --i){
		if(pa[x][i]!=pa[y][i]){
			x=pa[x][i];
			y=pa[y][i];
		}
	}
	return pa[x][0];
}

int len(int x, int y){
	int g = lca(x, y);
	return dp[x]-dp[g]+dp[y]-dp[g];
}
int nod;
map<int, int> mem[N];
int dfs1(int x, int pa){
	if(x==0){
		return 0;
	}
	if(mem[x].count(pa))return mem[x][pa];
	if(a[x].size()>2){
		return x;
	}
	int res = 0;
	if(a[x][0]==pa){
		res = dfs1(a[x][1], x);
	}
	else{
		res = dfs1(a[x][0], x);
	}
	mem[x][pa]=res;
	return res;
}
int main(){
// int t;cin>>t;while(t--){
	int q, x;
	scanf("%d%d",&n,&q);
	pa[1][0]=1;
	for(int i=2; i<=n; ++i){
		scanf("%d",&x);
		pa[i][0]=x;
		a[x].push_back(i);
		a[i].push_back(x);
	}
	dp[1]=1;
	for(int i=1; i<=n; ++i)dfs(i);
	pre();
	
	for(int i=1; i<=n; ++i){
		if(a[i].size()==1){
			a[i].push_back(0);
		}
	}
	int y;
	for(int i=0; i<q; ++i){
		scanf("%d%d",&x,&y);
		if(a[y].back()!=0){
			printf("yes\n");
		}
		else{
			int tmp = dfs1(y, 0);
			if(tmp==0){
				printf("no\n");
				continue;
			}
			int len1 = len(x, y);
			int len2 = len(tmp, x);
			int len3 = len(tmp, y);
			// cout<<tmp<<" "<<len1<<" "<<len2<<" "<<len3<<endl;
			if(len1 != len2 + len3){
				printf("no\n");
			}
			else{
				if(len3<len2){
					printf("yes\n");
				}
				else{
					printf("no\n");
				}
			}
		}
	}
// }
return 0;
}
Copy
Escape from TarkZoo Zain
GNU G++17
65 ms
23.1 MB
Wrong Answer