Company Queries II

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define vout(x) for(int i=0;i<(long long)x.size();i++) printf("%lld ",x[i]);

// g++ <filename>.cpp -g -Wall -Wextra -DDEBUG -o <executable>

// copied from: https://codeforces.com/blog/entry/79024
// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}

// === Debug macro ends here ===

const int MAX_DEPTH = 20;


int get_kth_ancestor(vector<vector<int>> &table, int node, int k) {

    for (int j = 0; j < MAX_DEPTH; j++) {
        if (k & (1 << j)) {
            node = table[j][node];
            if (node == 0) return -1;
        }
    }
    return node; 
};

int find_depth(vector<vector<int>> &table, int node) {
    int depth = 0;
    while (node != 0) {
        node = table[0][node];
        depth++;
    }
    return depth;
}

int find_lca(vector<vector<int>> &table, vector<int> &depth, int u, int v) {

    // 1. equalize depth
    if (depth[u] > depth[v]) {
        u = get_kth_ancestor(table, u, depth[u] - depth[v]);
    } else if (depth[v] > depth[u]) {
        v = get_kth_ancestor(table, v, depth[v] - depth[u]);
    }

    if (u == v) return u;

    // 2. move up node
    for (int j = MAX_DEPTH - 1; j >= 0; j--) {
        if (table[j][u] != table[j][v]) {
            u = table[j][u];
            v = table[j][v]; 
        }
    }


    return table[0][u];
}

signed main() {
    
    int n, q;
    cin >> n >> q;
    
    vector<vector<int>> table(MAX_DEPTH, vector<int>(n+1, 0));
    vector<int> depth(n+1, 0);

    for (int i = 2; i <= n; i++) {
        cin >> table[0][i];
        depth[i] = depth[table[0][i]] + 1;
    }

    for (int j = 1; j < MAX_DEPTH; j++) { 
        for (int i = 1; i <= n; i++) { 
            if (table[j-1][i] != 0) {
                table[j][i] = table[j-1][table[j-1][i]];
            }
        }
    }

    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;

        int lca = find_lca(table, depth, u, v);
        cout << lca << "\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