Изменения

Пусть <tex>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{inlabel} x \le \operatorname{inlabel} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям.Найдем <tex>b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>. {{Утверждение|statement= <tex>\operatorname{inlabel} (((x >> (i + 1)) << 1) | 1) << i</tex>, где <tex>i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)</tex>|proof= ?}}