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 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, 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 components 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!