Shared code

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n,q;
  cin>>n>>q;
  vector<vector<int>> adj(n);
  for (int i = 1; i < n; i++) {
    int par;
    cin>>par;
    par--;
    adj[par].push_back(i);
  }

  vector<int> depth(n);
  vector<int> pre_order(n);
  vector<int> time_in(n);
  vector<int> time_out(n);
  int timer = 0;
  auto dfs = [&](auto dfs, int u) -> void {
    time_in[u] = timer;
    pre_order[timer++] = u;
    for(int v : adj[u]) {
      depth[v] = 1 + depth[u];
      dfs(dfs, v);
    }
    time_out[u] = timer;
  };
  dfs(dfs, 0);

  vector<int> seg_tree(2 * n);
  for (int i = 0; i < n; i++) {
    seg_tree[n + i] = time_out[pre_order[i]];
  }
  for (int i = n-1; i >= 1; i--) {
    seg_tree[i] = max(seg_tree[2*i], seg_tree[2*i+1]);
  }

  auto lca = [&](int u, int v) -> int {
    if(time_in[u] > time_in[v]) swap(u, v);
    int l = 1, r = time_in[u]+1;
    while(l < r) {
      int w = r + n, b = __lg(min(w & -w, r - l));
      if (seg_tree[(w-1) >> b] <= time_in[v]) r -= 1 << b;
      else l = r - (1 << b) + 1;
    }
    return pre_order[l-1];
  };

  while(q--) {
    int u,v;
    cin>>u>>v;
    u--,v--;
    cout<<lca(u,v)+1<<'\n';
  }

  return 0;
}