Company Queries II

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

int MXN = (int)2e5+1;
int main() {
	int par[MXN];
	int depth[MXN];
	par[1] = 0;
	depth[1] = 0;
	int n, q;
	cin >> n >> q;
	for (int i=2; i<=n; i++) {
		int b;
		cin >> b;
		par[i] = b;
		depth[i] = depth[b] + 1;
	}

	for (int i=0; i<q; i++) {
		int a, b;
		cin >> a >> b;
		while (depth[a] > depth[b]) a = par[a];
		while (depth[b] > depth[a]) b = par[b];
		while (a != b) {
			a = par[a];
			b = par[b];
		}
		cout << a << endl;
	}

	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED