Изменения
Нет описания правки
Алгоритм позволяет найти ответы для дерева из <tex>n</tex> вершин и <tex>m</tex> запросов за время <tex>O (n + m)</tex>, то есть при достаточно большом <tex>m</tex>, за <tex>O (1)</tex> на запрос.
== Алгоритм ==
Подвесим наше дерево за любую вершину, и запустим [[Обход в глубину, цвета вершин|обход в глубину]] из еёнеё.Ответ на каждый запрос мы найдём в течение поиска в глубину. Ответ для вершин <tex>\langle v, </tex> и <tex> u \rangle </tex> находится, когда мы уже посетили вершину <tex>u</tex>, а так же посетили всех сыновей вершины <tex>v</tex>, и собираемся выйти из неё.
Зафиксируем момент: мы собираемся выйти из вершины <tex>v</tex> (обработали всех сыновей) и хотим узнать ответ для пары <tex>v</tex>, <tex>u</tex>.
