LCA online

Если мы для каждой вершины знаем её глубину в дереве (расстояние от корня), то вроде бы можно - следующим образом:

* вот нам поступили на вход две вершины a и b, тогда возьмём ту из них, которая глубже, и поднимем двоичным подъёмом до глубины другой вершины
* теперь, когда обе вершины одной высоты, мы можем уже заметить, что LCA находится от них на одном и том же расстоянии
* значит, будем идти двоичным подъёмом - если мы шагнули от обеих вершин вверх и пришли в одну и ту же вершину, то это LCA или его предок (в общем, надо попробовать подняться на меньше), а иначе, т.е. если этим шагом пришли в разные вершины - надо попробовать подняться на больше.