Store each vertex’s ancestors 1, 2, 4, 8, ... steps up, and any two vertices find their lowest common ancestor in O(log n) jumps.
This interactive visualization needs JavaScript.