Изменения

Таким образом, обработка одной вершины занимает <tex>O(\log n + k_v)</tex> времени, где <tex>k_v</tex> — количество отрезков в ответе, полученных из вершины <tex>v</tex>, всего посещенных вершин <tex>O(\log n)</tex>, итого <tex>O({\log}^2 n + k)</tex>. Препроцессинг выполняется за <tex>O(n {\log}^2 n)</tex> из-за вставки в дерево поиска.