Изменения
Нет описания правки
# Покраску дерева в $k$ цветов от 1 до $k$ назовем яркой, если между любыми двумя вершинами одного цвета $c$, существует вершина цвета $d$, что $d < c$. Рассмотрим функцию $f(n) = k$ {{---}} минимальное $k$, что любое дерево из $n$ вершин можно ярко покрасить в $k$ цветов. Докажите, что $f(n) = O(\log{n})$
# Задано дерево из $n$ вершин. В каждой вершине есть число. Нужно отвечать на запросы: медиана в множестве чисел, записанных в вершинах на пути. Время на запрос: $O(\log{n})$.
# Будет добавлено позжеРассмотрим подвешенное дерево.Пусть $s(v)$ {{---}} размер поддерева с корнем в вершине $v$, $C(v)$ {{---}} множество всех непосредственных потомков вершины $v$, $h(v) = \operatorname*{arg\,max}\limits_{u \in C(v)} s(u)$, $f(v) = s(v) - s(h(v))$. Доказать, что $\sum\limits_{v \in V}f(v) = O(n \log{n})$.# Рассмотрим подвешенное дерево. Пусть $k(v)$ {{---}} высота поддерева с корнем $v$, $C(v)$ {{---}} множество всех непосредственных потомков вершины $v$, $d(v) = \operatorname*{arg\,max}\limits_{u \in C(v)} k(u)$, $g(v) = \sum\limits_{\substack{ u \in C(v) \\ u \ne d(v)}} k(v)$. Доказать, что $\sum\limits_{v \in V}g(v) = O(n)$.
</wikitex>
