Company Queries II

#include <bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for (int i = a; i < b; i++)
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
typedef pair<long long, long long> pl;

const long long lmx = LLONG_MAX;
const int imx = INT_MAX;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    int levels = 0;
    while (pow(2, levels) < n) levels++;

    vector<vector<int>> anc(n, vector<int>(levels+1, 0));
    vector<int> boss(n);
    vector<int> level(n);
    anc[0][0] = 1;
    boss[0] = 1;
    level[0] = 0;

    REP(i, 1, n) {
        cin >> boss[i];
        level[i] = level[boss[i] - 1] + 1;
        anc[i][0] = boss[i];
    }

    REP(i, 1, levels + 1) {
        REP(j, 1, n) {
            if (anc[j][i - 1] != 0 && anc[anc[j][i - 1] - 1][i - 1] != 0) {
                anc[j][i] = anc[anc[j][i - 1] - 1][i - 1];
            } else {
                anc[j][i] = 0;
            }
        }
    }

    vector<pi> queries(q);
    REP(i, 0, q) {
        cin >> queries[i].F >> queries[i].S;
    }

    vector<int> ans(q);
    REP(i, 0, q) {
        int emp1 = queries[i].F, emp2 = queries[i].S;
        int lvl1 = level[emp1 - 1], lvl2 = level[emp2 - 1];
        int dif = abs(lvl1 - lvl2);

        if (lvl1 < lvl2) {
            for (int j = levels; j >= 0; j--) {
                if (dif >= (1 << j)) {
                    emp2 = anc[emp2 - 1][j];
                    dif -= (1 << j);
                }
            }
        } else if (lvl2 < lvl1) {
            for (int j = levels; j >= 0; j--) {
                if (dif >= (1 << j)) {
                    emp1 = anc[emp1 - 1][j];
                    dif -= (1 << j);
                }
            }
        }

        if (emp1 == emp2) {
            ans[i] = emp1;
            continue;
        }

        for (int j = levels; j >= 0; j--) {
            if (anc[emp1 - 1][j] != 0 && anc[emp1 - 1][j] != anc[emp2 - 1][j]) {
                emp1 = anc[emp1 - 1][j];
                emp2 = anc[emp2 - 1][j];
            }
        }
        ans[i] = anc[emp1 - 1][0];
    }

    REP(i, 0, q) cout << ans[i] << "\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