Source Code
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3", "omit-frame-pointer","inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,fma,popcnt,abm,mmx,avx,avx2")

#include <bits/stdc++.h>
using namespace std;

/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compiles and gets accepted.
 *  ___  __     _______    _______
 * |\  \|\  \  |\  ___ \  |\  ___ \
 * \ \  \/  /|_\ \   __/| \ \   __/|
 *  \ \   ___  \\ \  \_|/__\ \  \_|/__
 *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \
 *    \ \__\\ \__\\ \_______\\ \_______\
 *     \|__| \|__| \|_______| \|_______|
 */
//const long long mod = 1000000007;
const long long mod = 998244353;
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());

const int mxN = 300010;
const int lg = 23;
int par[mxN][lg];
int h[mxN];
vector<int> g[mxN];
void dfs(int v = 0, int p = -1) {
	h[v] = (p == -1 ? 0 : h[p] + 1);
	par[v][0] = p;
	for (int i = 1; par[v][i - 1] != -1; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u != p) dfs(u, v);
	}
}
int lca(int u, int v) {
	if (h[u] > h[v]) swap(u, v);
	for (int i = lg - 1; i >= 0; i--) {
		if (par[v][i] != -1 && h[par[v][i]] >= h[u]) v = par[v][i];
	}
	if (u == v) return u;
	for (int i = lg - 1; i >= 0; i--) {
		if (par[v][i] != par[u][i]) v = par[v][i], u = par[u][i];
	}
	return par[v][0];
}

int up[mxN];
int sm = -1;
int sm2 = -1;
void sv(int v = 0, int p = -1, int lst = -1) {
	int ch = g[v].size() - (p != -1 ? 1 : 0);
	if (ch >= 2) lst = v;
	if (ch >= 2 && (sm == -1 || h[sm] > h[v])) sm = v;
	if (ch >= 3 && v == 0) sm2 = 0;
	if (v != 0 && ch >= 2 && (sm2 == -1 || h[sm2] > h[v])) sm2 = v;
	up[v] = lst;
	for (auto u : g[v])
		if (u != p) sv(u, v, lst);
}

int main(int argc, char *argv[]) {
#ifdef ONLINE_JUDGE
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif

	srand(time(NULL));
	cout << fixed << setprecision(12);

	int t = 1;
//	int Case = 1;
//	cin >> t;
//	t = 10000;
	while (t--) {
		memset(par, -1, sizeof par);
		int n, q;
		cin >> n >> q;
		for (int i = 1, p; i < n; i++) {
			cin >> p, p--;
			g[p].push_back(i);
			g[i].push_back(p);
		}
		dfs();
		sv();
		for (int i = 0, a, b; i < q; i++) {
			cin >> a >> b;
			a--, b--;
			if (a == b) {
				cout << "yes\n";
			}
			// root
			if (b == 0 && sm == -1) {
				cout << "no\n";
				continue;
			}
			if (b == 0) {
				int d2 = h[a] - h[sm];
				int d3 = h[sm];
//				cerr << d3 << ' ' << d2 << '\n';
				cout << (d3 < d2 ? "yes" : "no") << '\n';
				continue;
			}
			// has children and a parent
			if (g[b].size() > 1) {
				cout << "yes\n";
				continue;
			}
			// leaf
			if (up[b] == -1) {
				cout << "no\n";
				continue;
			}
			int l = lca(a, b);
//			int d = h[a] + h[b] - 2 * h[l];
			int at = up[b];
			if (h[at] < h[l]) at = l;
			if (at == 0) {
				int at = sm2;
				if (at == -1) {
					cout << "no\n";
					continue;
				}
				int l2 = lca(a, at);
				int d2 = h[a] + h[at] - 2 * h[l2];
				int l3 = lca(b, at);
				int d3 = h[b] + h[at] - 2 * h[l3];
				cout << (d3 < d2 ? "yes" : "no") << '\n';
				continue;
			}
			int l2 = lca(a, at);
			int d2 = h[a] + h[at] - 2 * h[l2];
			int d3 = h[b] - h[at];
//			cerr << d2 << ' ' << d3 << '\n';
			cout << (d3 < d2 ? "yes" : "no") << '\n';
		}
	}
	return 0;
}

/* stuff you should look for:
 * overflow, array bounds
 * special cases (n=1?)
 * clear arrays
 * DON'T STICK TO ONE APPROACH
 * solve simpler or different variation
 * Solve DP using graph ( \_(-_-)_/ )
 */
Copy
Escape from TarkZoo Khaledkee
GNU G++17
67 ms
37.4 MB
Wrong Answer