LCA implementation

Debugging Help
#1

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!

#2

The answer is yes, though I don’t know what you mean by transitive. Let \text{path\_root}(v) denote the set of all vertices on the path from v to the root of the tree. Then for any nonempty set of vertices S, \text{lca}(S) is defined to be the unique vertex such that \bigcap_{v\in S}\text{path\_root}(v)=\text{path\_root}(\text{lca}(S)). As set intersection is associative and commutative it means that you can calculate the LCAs in any order you want and you’ll end up with the same result. For example,

\begin{align*} \text{path\_root}(\text{lca}(n_1,n_2,n_4))&=\text{path\_root}(n_1)\cap (\text{path\_root}(n_2)\cap \text{path\_root}(n_4))\\ &=(\text{path\_root}(n_1)\cap \text{path\_root}(n_2))\cap \text{path\_root}(n_4)\\ &=\text{path\_root}(n_3)\cap \text{path\_root}(n_4). \end{align*}
#3

I’ve already gone through the debug section. It is just that I can’t figure it out no matter what I do. I know that the dfs and lca functions are right. This means that the only portion that is wrong is the comb function. But I have no idea as to why it is wrong.

#4

Have you tried stress testing?

#5

I realized the stress testing I did wasn’t good enough. The test cases I created weren’t good enough. I created some better ones and figured out where I went wrong.

1 Like