Изменения

*: <tex>A1 </tex> - часть обхода до выбранного вхождения вершины <tex>c</tex>, включая ее.*: <tex>A2 </tex> - часть обхода после выбранного вхождения вершины <tex>c</tex>, включая ее.*Аналогично, выберем любое вхождение вершины <tex>g </tex> в эйлеров обход дерева <tex>T2 </tex> и разрежем его на 2 две части <tex>B1 </tex> и <tex>B2</tex>.*Соберем результирующий эйлеров обход в порядке <tex>A1 , B2 , B1</tex> (без первой повторяющейся вершины) , <tex>A2</tex>.

Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев <tex>T1 </tex> и <tex>T2</tex>, будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины, для построения дерева поиска, будет время посещения этой вершины эйлеровым обходом.Для каждой вершины дерева <tex>(T1, T2) </tex> будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. Тогда за <tex>O(1) </tex> переходим от вершины дерева к вершине дерева поиска, по которой за O(log n) можно будет разделить дерево поиска на 2 две части.