Изменения
Нет описания правки
# Обозначим как $A[v]$ число, в котором $i$-й бит равен $1$, если в $A(v)$ есть путь, заканчивающийся на расстоянии $i$ от корня. Считайте, что вы можете решить задачу о $m$ запросах $LCA$ в дереве с $n$ вершинами за $O(n+m)$ (например, используя алгоритм Фарах-Колтона и Бендера, см https://www.ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf). Объясните, как посчитать $A[v]$ за время $O(n+m)$.
# Назовем вершину $v$ большой, если $|A(v)| > \log n/\log\log n$ и маленькой в противном случае. Докажите, что число больших вершин не превышает $m \log\log n/\log n$. Указание: оцените число больших вершин на каждом уровне дерева. Отдельно рассмотрите большие вершины на нижних $\log\log n$ и на остальных уровнях.
# Для вершины $v$, для которой $|A(v) = k$ будем рассмотрим фрагменты путей, лежащие выше вершины $v$. Будем хранить $B(v) = [l_1, l_2, \ldots, l_k]$ - список глубин самых тяжелых ребер на фрагментах путях, проходящих через $v$, в порядке от самого длинного пути к самому короткому. Иначе говоря, пронумеруем пути из $A(v)$ в порядке возрастания глубины их верхней вершины. Тогда $l_i$ - расстояние от корня до ребра, которое является самым тяжелым на пути от $v$ до некоторой вершины $u_i$, которая является верхним концом $i$-го пути. Числа $l_i$ называются тагами, длина тага $O(\log\log n)$. Докажите, что массив $B(v)$ отсортирован по неубыванию.
# Пусть $p$ - родитель вершины $v$, как связаны массивы $B(p)$ и $B(v)$? Дайте подробное описание, используя, при необходимости, $A(p)$ и $A(v)$.
# Для больших вершин $B(v)$ помещается в $O(\log\log n)$ машинных слово. Пусть родитель вершины также большой. Предложите алгоритм пересчета $B(v)$ через $B(p)$, $A[p]$ и $A[v]$ за $O(\log\log n)$, перед этим можно выполнить общий для всех вершин предподсчет за $O(n+m)$.
