693
правки
Изменения
→remove(u,v)
Попробуем найти подходящую вершину <tex>x</tex> в <tex>T_u</tex> следующим образом:
# Если исходящее ребро ведёт в <tex>T_v</tex>, то выходим из цикла и добавляем ребро <tex>xy</tex> в остовные леса <tex>F_i</tex>, для которых <tex>i\leqslant l(xy)</tex> и выходим из цикла;
# Если исходящее ребро ведёт в другую вершину поддерева <tex>T_u</tex>, увеличиваем его уровень на <tex>1</tex>;
# Если есть непроверенные рёбра, переходим к пункту <tex>1</tex>;
'''Замечание.''' Увеличив уровень ребра на единицу, нужно не забыть обновить <tex>G_{i+1}</tex> и <tex>F_{i+1}</tex>.
====Оценка времени работы====
Пункт <tex>1</tex> работает за <tex>O(\log^2 n)</tex>, так как мы добавляем ребро на каждом уровне, а количество уровней не больше <tex>\log n</tex>.
Пункт <tex>2</tex> выполняется за <tex>O(\log n)</tex> и вызывается до <tex>\log n</tex> раз.
Пусть до момента, когда мы нашли нужное ребро, мы сделали <tex>S</tex> неудачных сканирований. Получаем сложность удаления одного ребра <tex>O(\log^2{n}+S\cdot\log n)</tex>. Для <tex>m</tex> вызовов процедуры <tex>\mathrm{remove(u, v)}</tex> сложность равна <tex>O(\log^2{n}\cdot m+\mathrm{\log}n\cdot\sum{S})</tex>, что не превосходит O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m). Отсюда суммарная сложность всех запросов равна O(\log^2{n}\cdot m)</tex>, а для одного запроса мы решаем задачу за <tex>O(\log^2{n}</tex>
====Псевдокод====
'''function''' remove ('''Node''' u, '''Node''' v): '''while''' i >= 0 e = <x, y> '''for''' y : e.level == i '''if''' y <tex>\in T_v</tex> '''for''' j = i '''downto''' 0 insert(<tex>F_j</tex>, e)
'''break'''
<!----При удалении возможны случаи:
