Source Code
//fold
#include <bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define tostr(x) static_cast<ostringstream&>((ostringstream()<<dec<<x)).str()
#define rep(i,begin,end) for(auto i = begin;i < end;i++)
#define repr(i,begin,end) for(auto i = begin-1;i >= end;i--)
#define pb push_back
#define sz(a) ((int)(a).size())
#define fi first
#define se second
#define abs(a) ((a) < (0) ? (-1)*(a) : (a))
#define SQ(a) ((a)*(a))
#define eqd(a,b) (abs(a-b)<1e-9)
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename t> t in(t q){cin >> q;return q;}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v){os << "[";for (int i = 0; i < sz(v); ++i) { os << v[i]; if (i != sz(v) - 1) os << ",";}os << "]";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const map<T, S>& v){for (auto it : v)os << "(" << it.first << ":" << it.second << ")";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const pair<T, S>& v){os << "(" << v.first << "," << v.second << ")";return os;}
const long double PI = acosl(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
//endfold
#define  N  (200'005)
#define MOD (1000000000ll + 7ll)
#define OO (1050000000)
#define OOL (1100000000000000000)

//global
vector<int> adj[N];
int d[N];
int f[N];
int l[N];
int e[25][N];

void dfs(int u, int p){
	e[0][u] = p;
	d[u] = d[p]+1;
	if(sz(adj[u]) > 2){
		if(f[p] == -1){
			f[u] = d[u];
		}else{
			f[u] = f[p];
		}
		l[u] = d[u];
	}else{
		f[u] = f[p];
		l[u] = l[p];
	}
	for(int v: adj[u]){
		if(v != p){
			dfs(v, u);
		}
	}
}

int cd(int a, int b){
	if(d[a] < d[b]) swap(a,b);
	for(int r = 24; r >= 0; r--){
		if(d[a]-(1<<r) >= d[b]){
			a = e[r][a];
		}
	}
	if(a == b){
		return d[a];
	}
	for(int r = 24; r >= 0; r--){
		if(e[r][a] != e[r][b]){
			a = e[r][a];
			b = e[r][b];
		}
	}
	return d[e[0][a]];
}

int main(){
	//fold
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cout << setprecision(10);
	//endfold
	int n,q;
	cin >> n >> q;
	rep(i,0,n-1){
		int v;
		cin >> v;
		adj[i+2].push_back(v);
		adj[v].push_back(i+2);
	}
	f[0] = l[0] = -1;
	d[0] = 0;
	dfs(1,0);
	e[0][0] = 0;
	rep(k,1,25){
		rep(i,0,n+1){
			e[k][i] = e[k-1][e[k-1][i]];
		}
	}
	rep(i,0,q){
		int a,b;
		cin >> a >> b;
		int ccd = cd(a,b);
		int le = d[a]+d[b]-2*ccd;
		int st;
		if(sz(adj[b]) > 1){
			st = 0;
		}else if(l[b] != -1 && l[b] >= ccd){
			st = d[b]-l[b];
		}else if(f[a] != -1 && f[a] >= ccd){
			st = le-(d[a]-f[a]);
		}else{
			st = le;
		}
		if(st*2 >= le && le > 0){
			cout << "no\n";
		}else{
			cout << "yes\n";
		}
	}
	return 0;
}
Copy
Escape from TarkZoo Adhami
GNU G++17
62 ms
24.0 MB
Accepted