Изменения
→Подготовка
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{chaininorder} v = \operatorname{order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
Пусть есть вершина <tex>u' \in S(i)</tex> такая, что <tex>\operatorname{order} u' = k'2^b</tex>.
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{chaininorder} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>\operatorname{order} u \hdots 2^{max}</tex>.
Рассмотрим два случая.
''Первый случай'' <tex>\operatorname{chaininorder} v = \operatorname{order} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{chaininorder}</tex> отличаютсяот <tex>\operatorname{chaininorder} v</tex>.
''Второй случай'' <tex>\operatorname{chaininorder} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex>Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{chaininorder} w = \operatorname{chaininorder} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{chaininorder} v' = \operatorname{chaininorder} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое.
}}
==Обработка запроса==
Пусть <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> принадлежат разным простым путям.
