74
правки
Изменения
Нет описания правки
Ответ на каждый запрос мы найдём в течение поиска в глубину. Ответ для вершин <tex>v</tex> и <tex>u</tex> находится, когда мы уже посетили вершину <tex>u</tex>, а так же посетили всех сыновей вершины <tex>v</tex>, и собираемся выйти из неё.
Зафиксируем момент: мы собираемся выйти из вершины <tex>v</tex> (обработали всех сыновей) и хотим узнать ответ для пары <tex>\langle v</tex>, <tex>u\rangle</tex>.
Тогда заметим, что ответ {{---}} это либо вершина <tex>v</tex>, либо какой-то её предок. Значит, нам нужно найти предка вершины <tex>v</tex>, который является предком вершины <tex>u</tex> с наибольшей глубиной. Заметим, что при фиксированном <tex>v</tex> каждый из предков вершины <tex>v</tex> порождает некоторый класс вершин <tex>u</tex>, для которых он является ответом, в этом классе содержатся все вершины которые находятся "слева" от этого предка.
