Изменения

Перейти к: навигация, поиск

Сведение задачи LCA к задаче RMQ

11 байт добавлено, 11:22, 13 июня 2012
Препроцессинг: fixup
#Cписок глубин посещенных вершин <tex>d</tex>. Глубина текущей вершины добавляется в конец списка при входе в данную вершину, а также после каждого возвращения из её сына.
#Список посещений узлов <tex>vtx</tex>, строящийся аналогично предыдущему, только добавляется не глубина а сама вершина.
#Значение функции <tex>I[u]</tex>, возвращающей любой индекс в списке глубин <tex>d</tex>, по которому была записана глубина вершины <tex>u</tex> (например при входе на момент входа в вершину).
=== Запрос ===
Анонимный участник

Навигация