Source Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

const int inf = 1e9;
const ll infll = 1e18;
const int M = 1e9 + 7;
const int N = 2e5;
int n, q, dp[N][19], deg[N], mn[N], depth[N];
vector<int> g[N];

void dfs(int x, int mnNode = -1, int p = -1){
	dp[x][0] = p;
	if(deg[x] > 2) mnNode = x;
	mn[x] = mnNode;
	for(auto u : g[x]){
		if(p == u)continue;
		depth[u] = depth[x] + 1;
		dfs(u,mnNode,x);
	}
}

int LCA(int u, int v){
	if(depth[u] > depth[v]) swap(u, v);
	for (int k = 18; k >= 0; --k){
		if(dp[v][k] == -1 || depth[dp[v][k]] < depth[u])continue;
		v = dp[v][k];
	}
	if(u == v) return u;
	for (int k = 18; k >= 0; --k){
		if(dp[v][k] == dp[u][k])continue;
		v = dp[v][k];
		u = dp[u][k];
	}
	return dp[u][0];
}
int dist(int u, int v){
	if(depth[u] > depth[v]) swap(u, v);
	int lca = LCA(u, v);
	return depth[u] - depth[lca] + depth[v] - depth[lca];
}
int main(){
	int n, q;
	scanf("%d%d", &n, &q);
	for (int u = 1,v; u < n; ++u){
		scanf("%d", &v);
		--v;
		// cout << u << " " << v << endl;
		g[u].pb(v);
		g[v].pb(u);
		++deg[u];
		++deg[v];
	}	
	int srce = 0;
	for (int i = 0; i < n; ++i){
		if(deg[i] > deg[srce]) srce = i;
	}
	memset(dp, -1 , sizeof dp);
	dfs(srce);

	for (int k = 1; k < 19; ++k){
		for (int i = 0; i < n; ++i){
			if(dp[i][k-1] == -1) continue;
			dp[i][k] = dp[dp[i][k-1]][k-1];
		}
	}
	while(q--){
		int u, v;
		scanf("%d%d",&u,&v);
		--u,--v;
		if(deg[v] >= 2 || u == v) {
			puts("yes");
			continue;
		}
		if(mn[v] == -1){//the tree is a chain
			puts("no");
			continue;
		}
		if(dist(v, mn[v]) >= dist(u, mn[v])) puts("no");
		else puts("yes");
	}

}	
Copy
Escape from TarkZoo Hambubger
GNU G++17
61 ms
30.8 MB
Accepted