!LA

Level ancestor¹ - базовая задача, в которой у нас есть корневое дерево и для заданной вершины v и числа k мы хотим знать k - ого предка вершины v.

Медленное решение

Для понимания сложного решения иногда полезно разобраться с самым медленным, но зато самым простым способом решить, а потом его улучшать. В этом конкретном случае мы можем обойти дерево с помощью dfs-а, и запомнить для каждой вершины ее предка, если они у нас ещё не хранятся, после чего просто k раз переходить из вершины в предка, чтобы получить искомый ответ. В худшем случае, то есть бамбуке, все это работает за O(n) на запрос и O(n) на предподсчет.

Бинарные подъемы

Медленное решение, конечно, хорошее, но есть что улучшать. Давайте увеличим кол-во предподсчета, вспомнив, что любое число представимо в виде суммы степеней двоек. Давайте для каждой вершины посчитаем подъем на все степени 2 от 1 до $\lceil {\log }_{2}n\rceil$. Сделать это можно легко с помощью динамического программирования, для $2^0$ мы записываем предка вершины, а для корня его же самого, что не разбираться с несуществующими вершинами, а для всех остальных уровней можно просто посчитать по формуле:$bin\_up[v][k]=bin\_up[bin\_up[v][k-1]][k-1]$ Теперь для того чтобы подняться на k мы просто ищем наибольшую степень 2, которая меньше, либо равна k и поднимаемся на нее, и получаем сложность $O({\log }_{2}n)$ с предподсчетом за $O(n{\log }_{2}n)$. Этот вариант лучше всего использовать на олимпиадах, ведь пишется быстро и легко, а следующие реализации, хоть и быстрее, но пишутся гораздо труднее и зачастую игра не стоит свеч.

Код

long long lev_anc(long long x, long long k) {
	long long cnt = 0;
	while (k) {
		if (k & 1) {
			x = bin_up[x][cnt];
		}
		k >>= 1;
		cnt++;
	}
	return x;
}

Ladder decomposition

Воспользуемся нашей замечательной декомпозицией. Теперь можно насчитать для каждой вершины бинарные подъемы из предыдущего пункта и весь этот предподсчет работает за $O(n{\log }_{2}n)$. Отлично, поймем теперь как отвечать на запросы за $O(1)$. Из вершины x мы можем подняться на $2^i\le k$ и попасть в вершину v. Утверждение. В пути $wa{y}_u$, в котором лежит v, обязательно лежит и ответ. Доказательство. Так как v лежит в пути $wa{y}_u$, то начало пути либо сам v, либо его предок. X потомок v, значит длина пути $wa{y}_v$ от v до конца $wa{y}_v$ хотя бы $2^i$, а значит длина пути от начала $wa{y}_v$ до v тоже хотя бы $2^i$. Тогда раз $2^{i+1}>k$, то и искомая вершина лежит в $wa{y}_v$. Получается, нам остается подняться на максимальную степень двух не превосходящую k¹ и подсчитать ответ за $O(1)$.

Прокачанный ladder decomposition

Заметим, что в ladder decomposition у нас ровно L путей, где L - кол-во листьев, что логично, ведь все пути заканчиваются в листьях и нет ни одного листа, в котором заканчивается 2 пути. Тогда давайте решим задачу только для листьев, а все запросы для нелистьев будем сводить к запросам от листьев. Для этого нам надо также подсчитать для каждой вершины ее листа потомка, что можно также сделать в dfs, а также считать бинапы только от листьев. Итоговая сложность предподсчета падает до $O(L{\log }_{2}n)$, а скорость ответа на запрос не меняется, ведь сводить запрос к листу можно за $O(1)$.

Macro-micro tree

Попробуем улучшить предыдущий алгоритм с помощью корнячки, а точнее одной из ее идей - деление объектов на легкие и тяжелые. Пусть S = $\lfloor \frac{{\log }_{2}n}{4}\rfloor$. Тогда пройдемся по всему графу и мысленно удалим вершину v, если $|v|<S$. Тогда у оставшегося дерева не более $\frac{n}{S}$ листьев, а значит, если мы на этой части дерева применим предыдущий алгоритм то получим сложность предподсчета, равную: $O\left(\frac{n}{S}{\log }_{2}n\right)=O\left(\frac{4n}{{\log }_{2}n}{\log }_{2}n\right)=O(n)$ У нас остались только поддеревья, мощность которых не превышает S. Утверждение. Количество таких деревьев не превышает $\sqrt{n}$. Доказательство. Сделаем эйлеров обход такого дерева, причем при каждом передвижении, если мы двигаемся вверх, то записываем в строку 1, иначе 0. После обхода мы получим бинарную строку длиной 2S - 2, а значит количество таких деревьев не превышает количества бинарных строк длины 2S, а их:$2^{2S}=2^{\frac{{\log }_{2}n}{2}}=n^{\frac{1}{2}}=\sqrt{n}$ Тогда давайте сделаем полный предподсчет для каждой вершинки во всех поддеревьях, мощность которых не превышает S, это будет работать за:$O(S^2\sqrt{n})=O\left(\frac{{\log }_2^{2}n}{16}\sqrt{n}\right)=O(\sqrt{n}{\log }_2^{2}n)=O(n)$

Примечание

Никогда не пишите этот алгоритм, он бессмысленен, ведь улучшается только предподсчет, для олимпиад это слишком сложно и долго писать и ограничения никогда не бывают такие жесткие, а в прод задачах о предподсчёте редко беспокоятся.

Footnotes

1. Не имеет нормального перевода, так что будет локализирована мной, как проблема уровня предка ↩ ↩²