!Ladder decomposition

Декомпозиция на дереве, позволяющая искать !LA на дереве за $O(1)$.

Описание

Сделаем то же, что и в long path decomposition, для каждой вершины в дереве мы насчитываем путь в потомка с самым глубоким поддеревом, при равенстве у двух вершин выбираем любую. После чего мы удлиняем в 2 раза все пути вверх и бахаем на это какую-нибудь структуру или насчитываем простейшие переходы для LA за $O(1)$. Построение выходит за кол-во ребер умноженное на 2, так как мы работаем с деревом, то сложность $O(n)$.

Советы по написанию

• Если путь при удлинении упирается в корень, то проще всего докинуть корень несколько раз, чтобы не создавать несуществующие вершины.
• Проще всего написать ссылку с каждой вершины на начало пути, а потом, когда посещаете начало пути, удлините путь в 2 раза вверх, все можно сделать за один обход dfs-a.

!Код