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