Изменения
Нет описания правки
# Дано взвешенное дерево. Научиться отвечать на запросы "вес ребра" и "прибавить ко всем ребрам на пути от $v$ до $u$ число $d$". После предобработки за $O(n)$ ответ на запрос за $O(\log{n})$.
# Алгоритм Хьюи. Дано дерево, вершины которого раскрашены в цвета, то есть задано отображение $col: V \to \{1..k\}$. С помощью LCA найти $dc: V \to \{1..k\}$, где $dc(u)$ - число различных цветов в поддереве с корнем в вершине $u$. Время работы: $O(V)$.
# Задано взвешенное дерево. Посчитать число простых путей в дереве длины от $L$ до $R$ и весом от $x$ до $y$. Время работы $O(n \log^2{n})$.# Задано невзвешенное дерево. Изначально все вершины белого цвета. Научиться отвечать на запросы: покрасить белую вершину в черную, к заданной вершине найти ближайшую черную вершину. Время работы одного запроса $O(\log{n})$.# Задано невзвешенное дерево. Изначально все вершины белого цвета. Научиться отвечать на запросы: покрасить белую вершину в черную, покрасить черную вершину в белую, к заданной вершине найти ближайшую черную вершину. Время работы одного запроса $O(\log^2{n})$.# Покраску дерева в $k$ цветов от 1 до $k$ назовем яркой, если между любыми двумя вершинами одного цвета $c$, существует вершина цвета $d$, что $d < c$. Рассмотрим функцию $f(n) = k$ {{---}} минимальное $k$, что любое дерево из $n$ вершин можно ярко покрасить в $k$ цветов. Докажите, что $f(n) = O(\log{n})$# Задано дерево из $n$ вершин. В каждой вершине есть число. Нужно отвечать на запросы: медиана в множестве чисел, записанных в вершинах на пути. Время на запрос: $O(\log{n})$.# Будет добавлено позже..
</wikitex>
