Company Queries II

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4const int MAXN=2e5;
5const int LOG=18;
6vector<int> adj[MAXN];
7int n, q, pa[MAXN][LOG], dep[MAXN];
8void dfs(int i) {
9  for(auto &x : adj[i]) {
10    if(x == pa[i][0]) continue;
11    pa[x][0] = i;
12    dep[x] = dep[i] + 1;
13    dfs(x);
14  }
15}
16int lca(int a, int b) {
17  if(dep[a] > dep[b])
18    swap(a, b);
19  for(int j=LOG-1; j>=0; --j) if(dep[pa[b][j]] >= dep[a])
20    b = pa[b][j];
21  if(a == b) return a;
22  for(int j=LOG-1; j>=0; --j) if(pa[a][j] != pa[b][j])
23    a = pa[a][j], b = pa[b][j];
24  return pa[a][0];
25}
26signed main(){
27  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
28  cin >> n >> q;
29  for(int i=1; i<n; ++i) {
30    int e; cin >> e; --e;
31    adj[e].emplace_back(i);
32    adj[i].emplace_back(e);
33  }
34
35  dep[0] = 0, pa[0][0] = 0;
36  dfs(0);
37  for(int j=0; j<LOG-1; ++j) for(int i=0; i<n; ++i)
38    pa[i][j+1] = pa[pa[i][j]][j];
39
40  while(q--) {
41    int a, b; cin >> a >> b;
42    cout << lca(--a, --b) + 1 << '\n';
43  }
44  return 0;
45}