Изменения

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

Алгоритм Тарьяна поиска LCA за O(1) в оффлайн

1516 байт добавлено, 22:52, 5 сентября 2019
м
Исправлена описка
Дано [[Дерево, эквивалентные определения | дерево ]] <tex> G </tex> и набор запросов: пары вершин <tex>\langle v, u \rangle </tex>, и для . Для каждой пары нужно найти наименьшего общего предка. Считаем, что все запросы известны заранее, поэтому будем решать задачу оффлайн.Алгоритм позволяет найти ответы для дерева из <tex>n</tex> вершин и <tex>m</tex> запросов за время <tex>O (n + m)</tex>, то есть при достаточно большом <tex>m</tex>, за <tex>O (1)</tex> на запрос.
== Алгоритм ==
Подвесим наше дерево за любую вершину, и запустим [[Обход в глубину, цвета вершин|обход в глубину]] из неё.
Ответ на каждый запрос мы найдём в течение поиска в глубину. Ответ для вершин <tex>v</tex> и <tex>u</tex> находится, когда мы уже посетили вершину <tex>u</tex>, а так же также посетили всех сыновей вершины <tex>v</tex>, и собираемся выйти из неё.
Зафиксируем момент: мы собираемся выйти из вершины <tex>v</tex> (обработали всех сыновей) и хотим узнать ответ для пары <tex>\langle v</tex>, <tex>u \rangle</tex>.
Тогда заметим, что ответ {{---}} это либо вершина <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]]
Классы этих вершин не пересекаются, а значит , мы можем их эффективно обрабатывать с помощью [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], которую будем хранить в массиве <tex>dsu</tex>.
Будем поддерживать также массив <tex>ancestorlcaClass[1 \dots n]</tex>, где <tex> ancestorlcaClass[w] </tex> {{---}} наименьший общий предок всех вершин, которые лежат в том же классе, что и <tex> w </tex>. Обновление массива <tex> ancestor lcaClass </tex> для каждого элемента будет неэффективно. Поэтому зафиксируем в каждом классе какого-то представителя этого класса. Функция <tex> \mathrm{find}(w) </tex> вернёт представителя класса, в котором находится вершина <tex> w </tex>. Тогда наименьшим общим предком всех вершин из класса <tex> w </tex> будет вершина <tex> ancestorlcaClass[\mathrm{find}(w)] </tex>.
Обновлять массив Обновление массива <tex> ancestor lcaClass </tex> будем производить следующим образом:* когда мы приходим в новую вершину <tex>v</tex> , мы должны добавить её в новый класс {{---}} <tex>ancestorlcaClass[v] = v</tex>* когда просмотрим всё поддерево какого-то ребёнка <tex> u </tex> у вершины <tex> v </tex>, мы должны объединить поддерево ребёнка с классом вершины <tex> v </tex> (<tex>\mathrm{union}(v, u, v)</tex> {{---}} объединить классы вершин <tex> v </tex> и <tex> u </tex>, а наименьшим общим предком представителя нового класса сделать вершину <tex> v </tex>). Система непересекающихся множеств сама определит представителя в зависимости от используемой нами эвристики. Нам надо лишь правильно установить значение массива <tex> ancestor lcaClass </tex> у нового представителя.
После того как мы обработали всех детей вершины <tex>v</tex>, мы можем ответить на все запросы вида <tex>\langle v, u \rangle </tex>, где <tex>u</tex> {{---}} уже посещённая вершина.
Нетрудно заметить, что <tex>lca(v, u) = ancestorlcaClass[\mathrm{find}(u)]</tex>. Для каждого запроса это условие (что одна вершина уже посещена, а другую мы обрабатываем) выполнится только один раз.
=== Реализация ===
'''function''' union(x : '''int''', y : '''int''', newAncestor : '''int'''):
leader = dsuUnion(x, y) <font color=green> // объединяем классы вершин <tex> x </tex> и <tex> y </tex> и получаем нового представителя класса </font>
ancestorlcaClass[leader] = newAncestor <font color=green> // устанавливаем нового предка представителю множества </font>
<font color=green>// можно запустить от любой вершины дерева.в самый первый раз</font>
'''function''' dfs(v : '''int'''):
visited[v] = ''true'' lcaClass[v] = v
'''foreach''' u : (v, u) '''in''' G
'''if''' '''not''' visited[u]
dfs(u)
union(v, u, v)
'''foreachfor''' (u : <tex>\langle v, u \rangle </tex> {{---}} есть такой запрос)
'''if''' visited[u]
запомнить, что ответ для запроса <tex>\langle v, u \rangle </tex> = ancestorlcaClass[find[u]]
== Корректность ==
Случай, когда <tex> u </tex> является наименьшим общим предком вершин <tex> u </tex> и <tex> v </tex> отработает , обработается правильно, потому что по алгоритму в этот момент <tex> ancestorlcaClass[\mathrm{find}(u)] = u </tex>.
ПредположимПусть теперь наименьшим общим предком вершин <tex> u </tex> и <tex> v </tex> будет вершина, что нашли отличная от этих двух. Во время обработки запроса алгоритм точно вернёт общего предкаэтих двух вершин, который не является наименьшимтак как он будет предком одной из вершин по массиву <tex> lcaClass </tex>, тогда это нас моментально приводит к противоречиюа предком другой из-за обхода в глубину.  Покажем, потому что запросмы должны были рассмотреть ранее {{---}} на минимальном предкенайдём наименьшего предка. Если он Пусть это не минимальный, значит, есть на какойтак. Тогда существует какая-то большей глубине, то есть такая вершина<tex> w </tex>, которая была посещена раньше и для которой условия на тоже является предком вершин <tex>u</tex> и <tex>v</tex> выполнялись, значити из которой мы вышли раньше во время обхода в глубину. Но тогда ситуация, что одна из вершин посещена, а у другой рассмотрены все дети, тогда должна была найтись эта вершина выполниться раньше, и в качестве ответа должна была вернуться вершина <tex> w </tex>. '''Замечание:''' для корректности алгоритма достаточно было бы одного массива <tex>LCAdsu </tex>, а представителем класса всегда выбирать наименьшего общего предка вершин класса. Это несложно сделать, так как мы всегда объединяем ребёнка со своим родителем. Но в таком случае алгоритм получился бы менее эффективным, потому что одна только эвристика сжатия путей работает недостаточно быстро.
== Оценка сложности ==
Она состоит из нескольких оценокчастей.
*Обход в глубину выполняет выполняется за <tex>O(n)</tex>.*Операции по объединению множеств, которые в сумме для всех разумных <tex>n</tex> затрачивают работают <tex>O (n)</tex> операцийвремени. Каждый запрос <tex>\langle v, u \rangle </tex> будет рассмотрен дважды {{---}} при посещении вершины <tex>u</tex> и <tex>v</tex>, но обработан лишь один раз, поэтому можно считать, что все запросы обработаются суммарно за <tex>O (m)</tex>.
*Для каждого запроса проверка условия и определение результата, опять же, для всех разумных <tex>n</tex> выполняется за <tex>O (1)</tex>.
Итоговая Следовательно, итоговая асимптотика получается {{---}} <tex>O (n + m)</tex>, но что при достаточно больших <tex>m</tex> ответ за составляет <tex>O (1)</tex> на один запрос. ==См. также==* [[Сведение задачи LCA к задаче RMQ]]* [[Heavy-light декомпозиция]]
== Источники информации ==
24
правки

Навигация