74
правки
Изменения
Нет описания правки
== Алгоритм ==
Подвесим наше дерево за любую вершину, и запустим обход в глубину из её.
Ответ на каждый запрос мы найдём в течении этого <tex>dfs'a</tex>. Ответ для вершин <tex>v</tex>,<tex>u</tex> находится, когда мы уже посетили вершины <tex>u</tex>, а в <tex>v</tex> обработали всех сыновей и собираемся выйти из неё.
Зафиксируем момент, мы собираемся выйти из вершины <tex>v</tex> (обработали всех сыновей) и хотим узнать ответ для пары <tex>v</tex>,<tex>u</tex>.
