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.net/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 findstrongly 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!
↵
But it is very well possible that you do not know about the [one somewhat advanced gym](https://codeforces.net/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
↵
We will cover more gyms from this old but gold series by Saint Petersburg State University in the future, so stay tuned!
