635
правок
Изменения
→Разрезание ребра
*Найдем в эйлеровом обходе дерева T две пары посещений концов удаляемого ребра gj и jg, которые соответствуют прохождениям по ребру (g, j) в T.
*Разрежем эйлеров обход дерева по этим парам на 3 части: A1, A2, A3
*Соберем результирующий обход в порядке В результате получатся 2 дерева с эйлеровыми обходами A1, A3, и A2соответственно
Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.
