Изменения
Нет описания правки
{{Утверждение
|statement=Если в начальном дереве есть ребро <tex>v\to u</tex> (<tex>u \in S(v)</tex>), то в построенном двоичном дереве
<tex>\operatorname{inorderinlabel} u \in S(\operatorname{inorderinlabel} v)</tex>
|proof=
}}
}}
Найдем вершину <tex>\operatorname{inorderinlabel} z</tex>, где <tex>z = LCA(x, y)</tex>. На прошлом шаге была найдена вершина
<tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>. Если бы в двоичном дереве были представлены все вершины,
то это и было бы ответом. Но такой вершины может не оказаться. Воспользуемся значениями <tex>\operatorname{ascendant} \operatorname{inlabel} x</tex> и <tex>\operatorname{ascendant} \operatorname{inlabel} y</tex>. Они характеризуют пути
