Изменения
→The Macro-Micro-Tree Algorithm
== The Macro-Micro-Tree Algorithm ==
В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.
Для начала рассмотрим алгоритм <tex>\langle O(L\log n + n), O(1)\rangle </tex> >, где <tex>L</tex> это количество листьев.
*С помощью обхода в глубину запомним по одному листу в ее поддереве для каждой вершины
*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.
В итоге полученный алгоритм действительно работает за <tex>\langle O(n), O(1)\rangle </tex> времени и за <tex>O(n)</tex> памяти.
== Сравнение с наивными реализациями ==
Используя DFS посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>,
