LCA

#include <cstdio>
#include <vector>
#include <cassert>

int p[LOG][MAXN];
vector<int> adj[MAXN];
int level[MAXN];
int _level;

void dfs(int node){
    ...
    level[node] = _level;
    _level++;
    ...
    for(...){
    }
    _level--;
}

int main(){
    int n, m;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        int val;
        scanf("%d", &val);
        p[0][i] = val;         // parent (level 0)
        adj[val].push_back(i); // adjacency list
    }
    // fill level, suppose root is 1
    dfs(1);

    // preprocess
    for(int i = 1; i < LOG; ++i)
        for(int j = 1; j <= n; ++j)
            p[i][j] = p[i - 1][p[i - 1][j]];

    int q;
    scanf("%d", &q);
    while(q--){
        int a, b;
        scanf("%d %d", &a, &b);
        // query
        if(level[a] > level[b]) swap(a, b); // lev[a] will be less than lev[b]
        for(int i = LOG - 1; i >= 0; --i)
            if(level[p[i][b]] >= leval[a])
                b = p[i][b];
        assert(level[a] == level[b]); // now lev[a] == lev[b] for sure.
        for(int i = LOG - 1; i >= 0; --i)
            if(level[p[i][b]] != level[p[i][a]]){
                a = p[i][a];
                b = p[i][b];
            }
        assert(a == b); // now a == b
        printf("%d\n", a);
    }
    return 0;
}