Company Queries II

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

// debug
template<class T> ostream& operator<<(ostream&, const vector<T>&);
template<class T> ostream& operator<<(ostream&, const set<T>&);
template<class T> ostream& operator<<(ostream&, const multiset<T>&);
template<class K, class V> ostream& operator<<(ostream&, const map<K, V>&);
template<class T, size_t N> ostream& operator<<(ostream&, const array<T, N>&);
template<class A, class B> ostream& operator<<(ostream& os, const pair<A, B>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<class T>
void print_collection(ostream& os, const T& v) {
    os << "{";
    bool first = true;
    for (const auto& x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << "}";
}
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { print_collection(os, v); return os; }
template<class T> ostream& operator<<(ostream& os, const set<T>& v) { print_collection(os, v); return os; }
template<class T> ostream& operator<<(ostream& os, const multiset<T>& v) { print_collection(os, v); return os; }
template<class K, class V> ostream& operator<<(ostream& os, const map<K, V>& v) { print_collection(os, v); return os; }
template<class T, size_t N> ostream& operator<<(ostream& os, const array<T, N>& v) { print_collection(os, v); return os; }
#define dbg(x) cerr << #x << " = " << (x) << '\n'

using ll = long long;
constexpr int INF = 1'000'000'000; // 1e9
constexpr ll LINF = 1'000'000'000'000'000'000LL; // 1e18
constexpr int MOD = 1'000'000'007; // 1e9 + 7

inline ll add(ll a, ll b) { return (a + b) % MOD; }
inline ll sub(ll a, ll b) { return ((a - b) % MOD + MOD) % MOD; }
inline ll mul(ll a, ll b) { return (a * b) % MOD; }


void solve() {
    int N, Q;
    cin >> N >> Q;

    const int LOG = 19; // 2*10^5 < 2^19

    // id, 2^j ancestor
    vector<vector<int>> parent(N + 1, vector<int>(LOG + 1, 0));
    vector<int> depth(N + 1, 0);

    for (int i = 2; i <= N; i++) {
        cin >> parent[i][0];

        depth[i] = depth[parent[i][0]] + 1;

        for (int j = 1; j <= LOG; j++) {
            parent[i][j] = parent[parent[i][j-1]][j-1];
        }
    }

    for (int i = 0; i < Q; i++) {
        int a,b;
        cin >> a >> b;

        if (depth[a] > depth[b]) {
            swap(a, b);
        }

        int diff = depth[b] - depth[a];
        for (int j = 0; j <= LOG; j++) {
            if (diff & (1 << j)) {
                b = parent[b][j];
            }
        }

        if (a == b) {
            cout << a << '\n';
            continue;
        }

        for (int j = LOG; j >= 0; j--) {
            if (parent[a][j] != parent[b][j]) {
                a = parent[a][j];
                b = parent[b][j];
            }
        }

        cout << parent[a][0] << '\n';
    }
}

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

    solve();

    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