Lowest Common Ancestor Training [Div. 1 Theory + Walkthrough]
Difference between en2 and en3, changed 28 character(s)
Codeforces has an excellent archive of training contests, named gyms!↵

But it is very well possible that you do not know about the [one somewhat advanced gym](https://codeforces.me/gym/100091) that I want to cover today, and the reason is that it is only available in Russian :| Or should I say "was" instead of "is"? :D↵

I translated the statements to English and added them to the contest materials. As usual, I also recorded a [problem walkthrough with theoretical material included](https://youtu.be/jkHHiQG5MqU), in case you ever get stuck or want to refresh the theory. ↵

First I describe the LCA problem itself and explain the binary lifting approach to solve it in $\langle \mathcal{O}(n \log n), \mathcal{O}(\log n) \rangle$. I then reduce LCA to RMQ, and use Sparse Table to solve RMQ in $\langle \mathcal{O}(n \log n), \mathcal{O}(1)\rangle$ afterwards. I also give a short preview of Farach--Colton and Bender's $\langle \mathcal{O}(n), \mathcal{O}(1)\rangle$  algorithm. Finally, we solve an involved problem where you have to find 
strongly connected componentbridges before finding LCA in the condensation graph.↵

We will cover more gyms from this old but gold series by Saint Petersburg State University in the future, so stay tuned!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English nskybytskyi 2021-01-13 18:42:37 28 Tiny change: 'e to find strongly connected components before f' -> 'e to find bridges before f'
en2 English nskybytskyi 2021-01-13 17:16:33 0 (published)
en1 English nskybytskyi 2021-01-13 17:16:26 1312 Initial revision (saved to drafts)