Company Queries II

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

const int N = 2e5+1;
int vis[N];
int first[N];
int depth[N];
vector<vector<int>> adj(N);

const int eN = 2*N - 1;
int tot[eN];

void dfs(int n, int& i, int d=1) {
    vis[n] = 1;
    depth[n] = d;
    if(!first[n])
        first[n] = i;
    tot[i++] = n;
    for(auto e : adj[n]) {
        if(!vis[e]) {
            dfs(e, i, d+1);
            tot[i++]=n;
        }
    }
}

const int K = 20;
int st[K+1][eN];

void buildST(int* s, int len) {
    copy(s, s+len, st[0]);
    
    for (int i = 1; i <= K; i++)
        for (int j = 0; j + (1<<i) <= len; j++) {
            int a = st[i-1][j];
            int b = st[i-1][j + (1<<(i-1))];
            st[i][j] = depth[a] <= depth[b] ? a : b;
        }
}

int queryST(int l, int r) {
    if(l > r) swap(l, r);
    int i = bit_width(r-l+1ul) - 1;
    int a = st[i][l];
    int b = st[i][r-(1<<i)+1];
    return depth[a] <= depth[b] ? a : b;
}

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

    for(int i = 2; i <= n; i++) {
        int e; cin >> e;
        adj[i].push_back(e);
        adj[e].push_back(i);
    }

    int i = 0;
    dfs(1, i);

    buildST(tot, i);

    while(q--) {
        int a, b;
        cin >> a >> b;
        cout << queryST(first[a], first[b]) << '\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