Company Queries II

#include <iostream>
#include <vector>

using namespace std;

void euler_tour_dfs(
    const vector<vector<int>>& children, 
    int node, 
    int depth, 
    vector<int>& euler_tour, 
    vector<int>& depth_array, 
    vector<int>& first_occurrence) 
{
    first_occurrence[node] = euler_tour.size();
    euler_tour.push_back(node);
    depth_array.push_back(depth);
    
    for (int child : children[node]) {
        euler_tour_dfs(children, child, depth + 1, euler_tour, depth_array, first_occurrence);
        euler_tour.push_back(node);
        depth_array.push_back(depth);
    }
}

int main() {
    
    int n, q;
    cin >> n >> q;
    
    // Build tree 
    vector<vector<int>> children(n + 1);
    for (int i = 2; i <= n; i++) {
        int boss;
        cin >> boss;
        children[boss].push_back(i);
    }
    
    // Euler tour arrays
    vector<int> euler_tour;
    vector<int> depth_array;
    vector<int> first_occurrence(n + 1);
    
    // DFS to build Euler tour
    euler_tour_dfs(children, 1, 1, euler_tour, depth_array, first_occurrence);
    
    // Build sparse table 
    int m = euler_tour.size();
    int log_m = 0;
    while ((1 << log_m) <= m) log_m++;
    vector<vector<int>> sparse_table(m, vector<int>(log_m));
    
    // Initialize sparse table
    for (int i = 0; i < m; i++) {
        sparse_table[i][0] = i;
    }
    
    // Complete sparse table
    for (int j = 1; j < log_m; j++) {
        for (int i = 0; i + (1 << j) <= m; i++) {
            int left = sparse_table[i][j - 1];
            int right = sparse_table[i + (1 << (j - 1))][j - 1];
            if (depth_array[left] <= depth_array[right]) {
                sparse_table[i][j] = left;
            } else {
                sparse_table[i][j] = right;
            }
        }
    }

    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        int l = first_occurrence[a];
        int r = first_occurrence[b];
        if (l > r) swap(l, r);
        
        int length = r - l + 1;
        int k = 0;
        while ((1 << (k + 1)) <= length) k++;
        
        int left_idx = sparse_table[l][k];
        int right_idx = sparse_table[r - (1 << k) + 1][k];
        
        if (depth_array[left_idx] <= depth_array[right_idx]) {
            cout << euler_tour[left_idx] << endl;
        } else {
            cout << euler_tour[right_idx] << endl;
        }
    }
}

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