Lowest Common Ancestor( Casually explained )
Difference between en2 and en3, changed 82 character(s)
Writing this tutorial to further my understanding in the RMQ topic LCA(Lowest Common Ancestor)↵

Prerequisites : DFS and similar( concept of depth and parent )↵

Definition: Given two nodes of a rooted tree, the first common ancestor they meet as they climb to their parents is the lowest common ancestor.↵

It’s needed to answer some tree queries like the smallest edge for the path U to V, or the largest edge or the sum, etc.↵

Theory : ↵
If we have an information table for each node like, ↵
for each node X, who is X’s 2^k th parent. If they exist, good, if not, -1.↵
how can we use this information to our advantage?↵
Suppose we want to know the largest edge from U to V↵
Naturally, we want to climb to the LCA of U and V, and while we’re climbing, we want to see the costs of each edge, and store the largest one.↵

but we don’t have to check all edges.↵
suppose, the node U has to climb 37 parents to reach its LCA with V.↵
now, 37’s binary is↵
100101 (32 + 4 + 1)↵
what we do is, from U, we directly know, the cost of going to 32nd(2^5th) parent, from the table we will build shortly. Then from there, we will choose the 32nd parent’s 4th parent, and then its parent.↵
so in total, we needed to have three comparison to not only climb to the LCA but also, calculate the max path length.↵

So how do we complete the rest of the algo? Well, first we pick U and V, and see who is deeper with respect to the root. We grab him , suppose U, and we make him climb, till he is in the same depth as V.↵
then until they both become the same, we make them both climb. ↵

How do we make them same depth? Well, the difference of their depth , turn it into a binary number and climb.↵

Btw, the table I was talking about is called sparse table. It's pretty neat.↵

So how do we implement this?↵
Let’s first just see if we can find LCA of two nodes U and V↵

1. Run a dfs and calculate a few things, for all X↵
depth[X] , parent[X]{for the root it’s -1}↵

2.↵

~~~~~↵
for(I = 1; I <= N; I++)sparse_table[I][0] = parent[I];↵
~~~~~↵



here, sparse_table[x][y] is X’s 2^Yth parent. ↵
-1 if it doesn’t exist.↵

Question, what’s the biggest 2^Y we can have, such that at least one node has 2^Y th parent?↵
floor(log2(n)) because, in worst case of a skewed tree of depth n, the last node’s greatest parent is↵
log2(n) and it can never be larger than that. So floor.↵

so we did some pre-processing with the sparse_table, we now know, the 2^0th parent of all the nodes.↵
now on to more↵

3.↵

~~~~~↵
for(I = 1; I <= N; I++)↵
   for(J = 1; (1 << J) < N; J++)↵
    if(sparse_table[U][I] !=-1 && sparse_table[U][I] != sparse_table[V][I])↵
        sparse_table[i][j] = sparse_table[sparse_table[i][j-1]][j-1];↵
~~~~~↵



The third line basically says↵
if, I has a 2^(j-1)th parent. Meaning, Suppose, ↵
j = 5. I = 1. Does, I have a 2^4th parent? Yes? Ok, then ↵
1’s 2^5th parent is 1’s 2^4th parent’s 2^4th parent.↵
because, 1’s 2^4th parent’s 2^4th parent is 2 x 2^4  = 2^5 ↵
this is the key relation that makes it N log N↵
so we have the sparse table ready. If you don’t get the above line, just draw a skewed tree with 9 nodes.↵
the last node’s 2^3 rd parent will be its 2^2nd parent’s 2^2nd parent.↵
Now time for the LCA function itself.↵

first. Make them same depth.↵
//we swap to make sure U is deeper than V ↵
find a number , log such that 2^(log+1) > depth[U]↵
F
~~~~~↵
f
or(I = log; I>=0; I--)↵
   if(depth[U] – (1 << I) >= depth[V])U = sparse_table[U][I];↵
~~~~~↵


If we can make this leap to U’s 2^I th parent, then do so, as long as U’s new depth is equal or deeper than V↵
Now, for trivial case, when LCA of U,V is V itself, ↵
climbing will make U equal to V, so if that happens,V is the answer.↵
Otherwise↵
F
~~~~~↵
f
or(I = log; i>=0; i--)↵
I   if(sparse_table[U][I] !=-1 && sparse_table[U][I] != sparse_table[V][I])↵
   
   U = sparse_table[U][I];↵
      V = sparse_table[V][I];↵
~~~~~↵


so what we just did was, if U’s 2^Ith parent exists, and their parents are not the same, then make them both climb.↵
currently, U and V are gonna be one step below their LCA, because of the condition we put↵
answer will be parent[U]↵

If you understood till this part, well, for the min cost, max cost,↵
just keep an extra info in the sparse_table, of ↵
cost_table[x][y]  = max or min cost of going to X’s 2^Yth parent. Rest should be easy for you.↵
thanks.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English Metalicana 2020-06-07 03:42:13 6 Tiny change: 'rse_table[U][I] !=-1)\n ' -> 'rse_table[I][J-1] !=-1)\n '
en8 English Metalicana 2020-05-15 22:50:54 44
en7 English Metalicana 2020-05-15 22:41:28 10
en6 English Metalicana 2020-05-15 22:38:49 82
en5 English Metalicana 2020-05-15 22:33:46 41 Tiny change: 'estor)\n\nPrerequisi' -> 'estor)\n\n#### Prerequisi'
en4 English Metalicana 2020-05-15 22:27:04 18
en3 English Metalicana 2020-05-15 22:16:55 82
en2 English Metalicana 2020-05-15 22:13:22 85
en1 English Metalicana 2020-05-15 21:58:18 4286 Initial revision (published)