Source Code
#include<bits/stdc++.h>
#define GO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef pair<int, int> pi;
const ll Mod = 998244353;
const ll INF = (ll)(1e18) + 5;
const ll N = 2e5 + 5, M = 18;

int n, m;
vec G[N];
bool isLeaf[N];

struct HLD {
	const int ON_EDGE = 0;

	int cur_pos;
	vector<int> parent, depth, heavy, head, pos, rpos;

	void init(int n) {
		cur_pos = 0;
		parent.resize(++n);
		head.resize(n);
		depth.resize(n);
		pos.resize(n);
		heavy.resize(n, -1);
		rpos.resize(n); // reverse mapping
		DFS(1, 0);
		decompose(1, 1);
	}

	int DFS(int u, int p) {
		parent[u] = p;
		int size = 1, mx = 0;
		for (int v : G[u]) if (v != p) {
			depth[v] = depth[u] + 1;
			int x = DFS(v, u);
			size += x;
			if (x > mx)
				mx = x, heavy[u] = v;
		}
		return size;
	}

	void decompose(int u, int h) {
		head[u] = h;
		rpos[pos[u] = ++cur_pos] = u;
		if (heavy[u] != -1)
			decompose(heavy[u], h);
		for (int v : G[u])
			if (v != parent[u] && v != heavy[u])
				decompose(v, v);
	}

	vector <pair<int, int>> getRanges(int u, int v) {
		int swaps = 0;
		vector <pair<int, int>> a, b;
		for (; head[u] != head[v]; v = parent[head[v]]) {
			if (depth[head[u]] > depth[head[v]])
				swap(u, v), swap(a, b), swaps++;
			b.emplace_back(pos[head[v]], pos[v]);
		}

		if (depth[u] > depth[v])
			swap(u, v), swap(a, b), swaps++;

		if (!(ON_EDGE && u == v))
			b.emplace_back(pos[u] + ON_EDGE, pos[v]);

		if (swaps & 1)
			swap(a, b);
		if (b.size() > 0)
			b[0].first *= -1;
		a.insert(a.end(), b.rbegin(), b.rend());
		return a;
	}
};

int main() {
	GO;
	int n, m; cin >> n >> m;
	for (int i = 2; i <= n; i++) {
		int j; cin >> j;
		G[i].push_back(j);
		G[j].push_back(i);
	}
	HLD hld;
	hld.init(n);
	auto rpos = hld.rpos;
	vec a(n + 1);
	for (int i = 1; i <= n; i++) {
		int u = rpos[i];
		a[i] = (G[u].size() > 2);
		a[i] += a[i - 1];
	}
	while (m--) {
		int u, v; cin >> u >> v;
		if (u == v || G[v].size() > 1) {
			cout << "yes\n"; continue;
		}
		auto R = hld.getRanges(v, u);
		int len = 0;
		for (auto& [l, r] : R)
			len += r - abs(l) + 1;
		if (len <= 3) {
			cout << "no\n"; continue;
		}
		len /= 2;
		bool ok = 0;
		bool down = 0;
		for (auto& [l, r] : R) {
			if (l < 0)
				down = 1, l *= -1;
			if (len <= r - l + 1) {
				if (down)
					r = l + len - 1;
				else l = r - len + 1;
				ok |= (a[r] - a[l - 1] > 0);
				break;
			}
			ok |= (a[r] - a[l - 1] > 0);
			len -= r - l + 1;
		}
		cout << (ok ? "yes" : "no") << '\n';
	}
	return 0;
}
Copy
Escape from TarkZoo Oxygen
GNU G++17
53 ms
36.3 MB
Accepted