Изменения

# Рассмотрим ветвящееся дерево, пусть в нем $n$ вершин. Пусть есть $m$ запросов на пары листьев, для которых необходимо найти максимальное ребро на пути. Разобьем каждый запрос на два запроса на вертикальном пути до $LCA$ этих листьев, таким образом имеем $2m$ вертикальных путей. Для вершины $v$ обозначим как $A(v)$ множество вертикальных путей, проходящих через $v$. Обозначим как $D_i$ множество вершин на расстоянии $i$ от корня, как $d_i$ число вершин на расстоянии $i$ от корня ($d_i=|D_i|$). Докажите, что $\sum\limits_{u\in D_i}\lceil\log(1+|A(u)|)\rceil<\sum\limits_{u\in D_i}\left(1+\log(1+|A(u)|)\right)\le d_i+d_i \log\frac{d_i+2m}{d_i}$.

# В условиях предыдущей задачи докажите, что $\sum\limits_{i\ge 0}\left(d_i + d_i\log\frac{d_i+2m}{d_i}\right)\le n+n\log\frac{n+2m}{n}+2n$.

# Обозначим как $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$ и на остальных уровнях.