Изменения
→Ассимптотика
====Ассимптотика====
* '''Память''': Для реализации алгоритма требуется <tex>O(n)</tex> памяти.
* '''Препроцессинг''': Heavyheavy-light декомпозиция строится за <tex>O(n)</tex>, вся дополнительная информация считается за <tex>O(1)</tex> для каждой из вершин.
* '''Запросы''': По свойству heavy-light декомпозиции, на пути от вершины к корню мы сменим не более <tex>\log n</tex> путей. Значит время выполнения запроса также <tex>O(\log n)</tex>.
