Company Queries II

#include <iostream>
#include <cmath>
#include <vector>
#include <tuple>
using namespace std;
// #define int long long int
#include <limits>
 
const int INF = std::numeric_limits<int>::max();
 
vector<int> ni, ds, r;
vector<vector<int>> g;
vector<pair<int, int>> min_tree;
pair<int, int> res;
int n, m, k;
 
void dfs(int v, int d) {
    ni.push_back(v);
    ds.push_back(d);
    if (r[v] == -1) {
        r[v] = ni.size() - 1;
    }
    for (int w: g[v]) {
        dfs(w, d + 1);
        ni.push_back(v);
        ds.push_back(d);
    }
}
void build_tree_min() {
    for (int i = 0; i < m; i++) {
        min_tree[k + i] = {ds[i], i};
    }
    for (int i = k - 1; i > 0; i--) {
        min_tree[i] = min(min_tree[2 * i], min_tree[2 * i + 1]);
    }
}
pair<int, int> answer_min(int a, int b) {
    res = {INF, -1};
    a += k;
    b += k;
    while (a <= b) {
        if (a % 2 == 1) {
            res = min(res, min_tree[a]);
            a++;
        }
        if (b % 2 == 0) {
            res = min(res, min_tree[b]);
            b--;
        }
        a /= 2;
        b /= 2;
    }
    return res;
}
 
int main() {
    int q;
    cin >> n >> q;
    g.resize(n);
    r.resize(n, -1);
    int v;
    for (int i = 0; i < n - 1; ++i){
        cin >> v;
        g[v - 1].push_back(i + 1);
    }
 
    dfs(0, 0);
 
    m = ni.size();
    k  = pow(2, ceil(log2(m)));
    min_tree.resize(2 * k, {INF, -1});
    build_tree_min();
 
    int a, b;
    for (int i = 0; i < q; i++) {
        cin >> a >> b;
        a--;
        b--;
        res = answer_min(min(r[a], r[b]), max(r[a], r[b]));
        cout << ni[res.second] + 1 << endl;
    }
    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