LCA

#include <bits/stdc++.h>

using namespace std;

ifstream fin("lca.in");
ofstream fout("lca.out");

int K, N, Q;
vector < vector < int > > Graph;
vector < int > Euler, lg, first, Level, rmq[18];

void DFS(int node, int level) {
    Euler[++K] = node;
    Level[K] = level;
    first[node] = K;
    for(int next : Graph[node]) {
        DFS(next, level + 1);
        Euler[++K] = node;
        Level[K] = level;
    }
}

void RMQ() {
    for(int i = 2; i <= K; ++i)
        lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= K; ++i)
        rmq[0][i] = i;
    for(int i = 1; (1 << i) < K; ++i)
        for(int j = 1; j <= K - (1 << i); ++j) {
            int l = 1 << (i - 1);
            rmq[i][j] = rmq[i - 1][j];
            if(Level[rmq[i - 1][j + l]] < Level[rmq[i][j]])
                rmq[i][j] = rmq[i - 1][j + l];
        }
}

int LCA(int u, int v) {
    int x = first[u], y = first[v];
    if(x > y)
        swap(x, y);
    int diff = y - x + 1,
        l = lg[diff],
        sol = rmq[l][x],
        sh = diff - (1 << l);
    if(Level[sol] > Level[rmq[l][x + sh]])
        sol = rmq[l][x + sh];
    return Euler[sol];
}

int main() {
    fin.sync_with_stdio(false);
    fout.sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    fin >> N >> Q;
    Graph.resize(N + 1);
    first.resize(N + 1);
    Euler.resize((N << 1) + 1);
    lg.resize((N << 1) + 1);
    Level.resize((N << 1) + 1);
    for(int i = 0; i < 18; ++i)
        rmq[i].resize((N << 1) + 1);
    for(int i = 2; i <= N; ++i) {
        int x;
        fin >> x;
        Graph[x].emplace_back(i);
    }
    DFS(1, 0);
    RMQ();
    while(Q--) {
        int u, v;
        fin >> u >> v;
        fout << LCA(u, v) << '\n';
    }
}