Company Queries II

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    int maxLog = ceil(log2(n)) + 1;
    vector<vector<int>> ancestor(n + 1, vector<int>(maxLog, 0));
    vector<int> level(n + 1, 0);
    vector<int> boss(n + 1, 0);

    for(int i = 2; i <= n; i++){
        cin >> boss[i];
        level[i] = level[boss[i]] + 1;
        ancestor[i][0] = boss[i];
    }

    for(int j = 1; j < maxLog; j++){
        for(int i = 1; i <= n; i++){
            ancestor[i][j] = ancestor[ancestor[i][j-1]][j-1];
        }
    }

    while(q--){
        int x, y;
        cin >> x >> y;

        if(level[x] < level[y]) swap(x, y);

        int diff = level[x] - level[y];
        for(int i = 0; i < maxLog; i++){
            if(diff & (1 << i)){
                x = ancestor[x][i];
            }
        }

        if(x != y){
            for(int i = maxLog - 1; i >= 0; i--){
                if(ancestor[x][i] != ancestor[y][i]){
                    x = ancestor[x][i];
                    y = ancestor[y][i];
                }
            }
            x = ancestor[x][0];
        }

        cout << x << "\n";
    }

    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: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED