Изменения
Исправлены некоторые ошибки, сделал так, как в оригинальной статье
{{Утверждение
|statement=<tex>\operatorname{inlabel} v = 2^i \bigg\lfloor \dfrac{\operatorname{preOrder} v + \operatorname{size} v}{2^i}\bigg\rfloor</tex>, где <tex>i = \lfloor\log_2 ((\operatorname{preOrder} - 1) v \oplus (\operatorname{preOrder} v + \operatorname{size} v - 1)) \rfloor + 1</tex>
|proof=
Посмотрим на <tex>A = (\operatorname{preOrder} v - 1) \oplus (\operatorname{preOrder} v + \operatorname{size} v - 1)</tex>.
}}
Посчитаем для каждого <tex>\operatorname{inlabel} v</tex> множество всех его потомков предков в <tex>B</tex> по основным ребрам. Заметим, что для хранения одного потомка предка достаточно хранить только его высоту в дереве. Чтобы восстановить его значение, нужно просто подняться на <tex>\Delta h</tex> вверх от вершины <tex>v</tex>. Поэтому, все это множество можно уместить в целое число: <tex>i</tex>-й бит будет единицей, если есть потомок предок на высоте <tex>i</tex>. Назовем это число, отвечающее множеству предков, <tex>\operatorname{ascendant} v</tex>.
В дальнейшем <tex>\operatorname{ascendant} v </tex> поможет в поиске <tex>LCA(\operatorname{inlabel} v, \operatorname{inlabel} u)</tex>. Также, нам понадобится еще следующая информация. <tex>\operatorname{head} v</tex> {{---}} самая не глубокая вершина <tex>u</tex> такая, что <tex>\operatorname{inlabel} v = \operatorname{inlabel} u</tex>. <tex>\operatorname{level} v</tex> {{---}} глубина вершины <tex>v</tex> в <tex>T</tex>.
