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