Изменения
Нет описания правки
Тогда заметим, что ответ {{---}} это либо вершина <tex>v</tex>, либо какой-то её предок. Значит, нам нужно найти предка вершины <tex>v</tex>, который является предком вершины <tex>u</tex> с наибольшей глубиной. Заметим, что при фиксированном <tex>v</tex> каждый из предков вершины <tex>v</tex> порождает некоторый класс вершин <tex>u</tex>, для которых он является ответом, в этом классе содержатся все вершины которые находятся "слева" от этого предка.
На рисунке разные цвета {{---}} разные классы,а белые вершины ещё не просмотренные в <tex>dfs</tex>.
Классы этих вершин не пересекаются, а значит мы их можем эффективно обрабатывать с помощью [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], которую будем храниться в массиве <tex>dsu</tex>.
'''int''' dsuGet(v : '''int'''):
'''if''' (v == dsu[v])
'''return''' v
'''else'''
'''function''' union(a : '''int''', b : '''int''', newAncestor : '''int''' ):
a = dsuGet(a)
b = dsuGet(b)
'''for''' i = 0 '''to''' query[v].size - 1
'''if''' visited[query[v][i]]
запомнить, что ответ для запроса (v,u) = ancestor[dsu_get(dsuGet[q[v][i])]]
== Оценка сложности ==
