3622
правки
Изменения
→Алгоритм
Тогда заметим, что ответ {{---}} это либо вершина <tex>u</tex>, либо какой-то её предок. Значит, нам нужно найти предка вершины <tex>v</tex>, который является предком вершины <tex>u</tex> с наибольшей глубиной. Заметим, что при фиксированном <tex>v</tex> каждый из предков вершины <tex>v</tex> порождает некоторый класс вершин <tex>u</tex>, для которых он является ответом, в этом классе содержатся все вершины, которые находятся "слева" от этого предка.
На рисунке разные цвета {{---}} разные непосещённые вершины раскрашены в белый цвет, а посещённые разбиты на классы, а белые вершины {{---}} ещё не просмотренные в <tex>dfs</tex>каждому из которых соответствует свой цвет.
[[file:mytree.png|500px|разные цвета {{---}} разные классы, а белые вершины ещё не просмотренные в dfs]]
