So based on what CP handbook had to say about finding the LCA using tree depths, here is my implementation.

## My implementation

```
#include <bits/stdc++.h>
using namespace std;
const int mxn=2e5+1;
int n,q,depth[mxn],first[mxn],timer=1,euler[2*mxn];
vector<int> adj[mxn];
struct SEG{
int N;vector<int> tree;
SEG(int N_){ N=N_+1;tree.resize(2*N,1e9); }
int comb(int a, int b){ return depth[a]<depth[b]? a:b; }
void pull(int p){ tree[p]=comb(tree[2*p],tree[2*p+1]); }
void update(int p, int val){ tree[p+=N]=val;for(p/=2;p;p/=2) pull(p); }
int query(int l, int r){
int ll=1e9, rr=1e9;
for(l+=N,r+=N+1;l<r;l/=2,r/=2){
if(l&1) ll=comb(ll,tree[l++]);
if(r&1) rr=comb(rr,tree[--r]);
}
return comb(ll,rr);
}
};
void dfs(int node, int parent, int d=0){
first[node]=timer;
euler[timer++]=node;
depth[node]=d;
for(int i: adj[node]){
if(i!=parent){
dfs(i,node,d+1);
euler[timer++]=node;
}
}
}
int lca(int a, int b, SEG s){
return s.query(min(first[a],first[b]), max(first[a],first[b]));
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for(int i=1;i<n;i++){
int a; cin >> a;
adj[a].push_back(i);
adj[i].push_back(a);
}
dfs(1,0);
SEG seg(2*n-1);
for(int i=1;i<2*n;i++)
seg.update(i, euler[i]);
while(q--){
int a, b;cin >> a >> b;
cout << lca(a,b,seg)<<'\n';
}
}
```

Note that the stuff in the main function is for solving this problem; CSES - Company Queries II. Now, I’m pretty sure that my implementation is wrong as I keep getting the wrong output. The segment tree is just basically finding the node with the least depth (which will be the LCA) between the first occurrence in the Euler tour of each of the nodes in which we are trying the find the LCA. I was wondering if you could tell me where I went wrong in implementing the Euler tour.

Also, another question about LCA’s. Suppose we have nodes n_1, n_2. Suppose that the LCA of them is n_3. Now suppose we have another arbitrary node n_4. Is the LCA of n_3 and n_4 also the LCA of n_1,n_2, and n_4? In other words, are LCA’s transitive. If it is, I was wondering if you could give me a proof.

Thanks!