\documentclass[12pt]{article}
\input{structure.tex}

\begin{document}

\renewcommand{\tl}{$2$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Анализ. ДЖАНКИ}
\renewcommand{\header}{
	ЛАГЕР ШКОЛА ЗА\\
	ПОДГОТОВКА НА РАЗШИРЕНИТЕ ОТБОРИ\\
	София, 27 юни 2026 г.\\
	Анализ на задачите
}
~\\

Отрязването на клон премахва цяло поддърво. Затова за всеки връх изборът е: на кой ден да го „отрежем“ от родителя му. Една групичка джанки във връх $u$ се обира добре узряла точно когато поддървото, съдържащо $u$, се отдели на ден $d_u$. По всеки коренно-листов път дните на отрязване трябва да са \textbf{ненамаляващи} надолу (по-долните части падат не по-късно от по-горните), а целта е максимална обща стойност на обраните джанки.

\section*{Динамика по поддървета}
Нека $f(v, t)$ е максималната печалба в поддървото на $v$, ако всички отрязвания в него стават в дни $\leq t$. За фиксиран връх $f(v, \cdot)$ е \textbf{ненамаляваща стъпаловидна функция} на $t$. Пазим я като асоциативен масив (\texttt{map}) от ден към \emph{нарастването} на $f$ в този ден.

\textbf{Сливане на деца.} $f(v,\cdot)$ е сумата на функциите на децата плюс приноса на джанките във $v$. Сумата на стъпаловидни функции = обединение на масивите им със събиране на стойностите по съвпадащи ключове; правим го по схемата „малко към голямо“ (по-малкият масив се влива в по-големия).

\textbf{Добавяне на джанките $(d_v, w_v)$.} Добавяме $+w_v$ в ден $d_v$, след което „поглъщаме“ толкова от следващите нараствания, колкото е $w_v$ (намаляваме ги и махаме изчерпаните ключове). Така поддържаме горната обвивка: печалбата $w_v$ се реализира само ако отрязваме на ден $\geq d_v$, измествайки по-късни, но по-слаби възможности.

Отговорът е сборът на всички нараствания в корена (т.е.\ $f(1, +\infty)$). Общата сложност е $O(n \log^2 n)$.

\section*{Подзадачи}
\textbf{Подзадача 1 ($n,k \leq 20$, $w_j=1$; 5 точки)} и \textbf{Подзадача 5 ($k \leq 20$, $w_j=1$; 13 точки).} Директна динамика $f(v, t)$ по всички дни $t \leq k$: за всеки връх $O(k)$ състояния, общо $O(nk)$.

\textbf{Подзадача 2 (джанки само в листата; 3 точки).} Всяко листо се обира независимо в своя ден; внимава се само за съвместимостта по пътя нагоре.

\textbf{Подзадача 3 (дървото е път, $w_j=1$; 9 точки).} По линеен граф задачата се свежда до най-дълга ненамаляваща подредица по дни.

\textbf{Подзадача 4 ($k \leq 2$; 10 точки).} Само два възможни дни -- разглеждат се малкото случаи.

\textbf{Подзадача 6 ($m \leq 1\,000$; 11 точки).} Достатъчна е по-груба динамика върху срещащите се дни, $O(m^2)$.

\textbf{Подзадача 7 ($w_j=1$; 19 точки)} и \textbf{Подзадача 8 (без ограничения; 30 точки).} Пълното решение със стъпаловидните функции и сливане „малко към голямо“; компресия на дните при нужда.

\end{document}
