Company Queries II

input/code.cpp: In function 'int main()':
input/code.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'ull' {aka 'long long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0; i<q; i++){
      |                  ~^~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#include <bit>

ll n;
ll d[2*200000+1];
ll f[2*200000+1];
ll e[2*(2*200000+1)];
ll didx = 0;
#define logn_max 20
ll rmq[2*(2*200000+1)*logn_max];
map<ll,vector<ll>> adj;

void dfs(ll a, ll di){
    d[a] = di;
    f[a] = didx;
    e[didx++] = a;
    if(adj.count(a)){
        for(auto b : adj[a]){
            dfs(b, di+1);
            e[didx++] = a;
        }
    }
}

void makermq() {
    for(ll i=0; i<didx; i++){
        rmq[i*logn_max + 0] = i;
    }
    for(ll j=1; (1<<j)<=didx; j++){
        for(ll i=0; i+(1<<j)<=didx; i++){
            ll l = rmq[i*logn_max + j - 1];
            ll r = rmq[(i + (1 << (j - 1)))*logn_max + (j-1)];

            ll ln = e[l];
            ll rn = e[r];

            rmq[i*logn_max + j] = d[ln] < d[rn] ? l : r;
        }
    }
}

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

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

    dfs(1, 1);
    makermq();

    for(int i=0; i<q; i++){
        ll qa, qb;
        cin >> qa >> qb;

        ll a = f[qa];
        ll b = f[qb];
        if (a > b) swap(a, b);

        ll l = b - a + 1;
        ll k = floor(log2(l));

        ll li = rmq[a * logn_max + k];
        ll ri = rmq[(b - (1 << k) + 1) * logn_max + k];

        int ln = e[li];
        int rn = e[ri];

        cout << e[(d[ln] < d[rn]) ? li : ri] << 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