Module Lowest common ancestor (LCA)

Lowest common ancestor (LCA)

**Frequency: 8/10** In many cases where a problem involves querying a path on a tree, there is a high likelihood that the Lowest Common Ancestor (LCA) will be a crucial element in the solution. There are also a lot of problems involving LCA in the next module, Euler tour.

Resources

- [CP Algorithms: Lowest Common Ancestor - Binary Lifting](https://cp-algorithms.com/graph/lca_binary_lifting.html)

Problems

LCA 589 / 594 1300
Distance query 524 / 537 1400
Robot on tree 442 / 468 1400
Heaviest edge 425 / 432 1500
Equal path 323 / 344 1500
Triplet 280 / 285 1500
Path update 326 / 334 1600
Second best minimum spanning tree 164 / 260 1700
Oggy and the cockroaches 55 / 84 1800