LCA

#include <bits/stdc++.h>
using namespace std;
ifstream in("lca.in");
ofstream out("lca.out");
const int nax = 200005;

vector<int> adj[nax];
int logaritm[3 * nax];

vector<pair<int,int>> euler;
vector<int> first(nax);
vector<vector<int>> rmq(nax * 3, vector<int> (20, 0));

void dfs(int node, int prd, int lvl) {
    first[node] = euler.size();
    euler.push_back({node, lvl});
    for(auto it : adj[node]) {
        if(it == prd) {
            continue;
        }
        dfs(it, node, lvl + 1);
        euler.push_back({node, lvl});
    }
}

void computeMins() {
    int n = euler.size();
    for(int i = 0; i < n; ++i) {
        rmq[i][0] = i;
    }
    for(int i = 1; (1 << i) <= n; ++i) {
        for(int j = 0; j + (1 << i) - 1 < n; ++j) {
            int k = rmq[j][i - 1];
            int l = rmq[j + (1 << (i - 1))][i - 1];
            if(euler[k].second < euler[l].second) {
                rmq[j][i] = k;
            } else {
                rmq[j][i] = l;
            }
        }
    }
}
int findLCA(int x, int y) {

    x = first[x];
    y = first[y];

    if(x > y) {
        swap(x, y);
    }
    int len = logaritm[y - x + 1];
    int k = rmq[x][len];
    int l = rmq[y - (1 << len) + 1][len];
    if(euler[k].second < euler[l].second) {
        return euler[k].first;
    }
    return euler[l].first;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    logaritm[1] = 0;
    for(int i = 2; i < nax; i++) {
        logaritm[i] = logaritm[i / 2] + 1;
    }

    int n, m;
    in >> n >> m;

    for(int i = 2; i <= n; ++i) {
        int x;
        in >> x;
        adj[x].push_back(i);
        adj[i].push_back(x);
    }

    dfs(1, 0, 0);
    computeMins();

    for(int i = 1; i <= m; ++i) {
        int x, y;
        in >> x >> y;
        out << findLCA(x, y) << '\n';
    }

    return 0;
}