Company Queries II

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

constexpr int N = 200005, LOG = 20;
vector<int> e[N];
int f[N][LOG], d[N];

void DFS(int uno, int fno)
{
    f[uno][0] = fno;
    d[uno] = d[fno] + 1;
    for (int i = 1; i < LOG; i++) 
    {
        f[uno][i] = f[f[uno][i-1]][i-1];
    }
    for(int v: e[uno]) 
    {
        if (v == fno) continue;
        DFS(v, uno);
    }
}

int LCA(int x, int y) 
{
    if (d[x] > d[y]) swap(x, y);
    int tmp = d[y] - d[x];
    for (int i = 0; tmp; i++, tmp >>= 1) if (tmp & 1)
    {
        y = f[y][i];
    }
    if(y == x) return y;
    for (int i = LOG - 1; i >= 0 && y != x; i--) 
    {
        if (f[x][i] != f[y][i]) 
        {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[y][0];
}

int main() 
{
    // cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    for (int i = 2; i <= n; i++) 
    {
        int x;
        cin >> x;
        e[i].push_back(x);
        e[x].push_back(i);
    }

    DFS(1, 0);
    while(q--)
    {
        int a, b;
        cin >> a >> b;
        cout << LCA(a, b) << 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