Козак Вус та дерево#100

Козак Вус та дерево (Editorial)

Перефразуємо задачу: пофарбувати вершину в чорний — це фактично «вилучити» її, бо ребро яскраве лише коли обидва його кінці білі. Отже, треба вибрати множину вершин мінімального розміру так, щоб сумарна вага ребер, у яких жоден кінець не належить , не перевищувала .

Оскільки запитів багато, а дерево одне, вигідно порахувати відразу всю залежність: нехай — мінімальна можлива сумарна вага яскравих ребер, якщо пофарбувати рівно вершин. Функція незростаюча, тому відповідь на запит — це найменше з f(j) \le k, яке знаходиться двійковим пошуком.

Величину рахуємо рюкзаком на дереві. Стан:

\mathrm{dp}[v][j][c] = \text{мінімальна вага яскравих ребер у піддереві } v,

де — скільки вершин піддерева пофарбовано, а c \in \{0, 1\} — колір самої вершини (біла чи чорна).

Обробка дитини з ребром ваги : об'єднуючи з , до суми додається тоді й лише тоді, коли обидві вершини і білі. Тобто перехід — звичайна згортка двох масивів за кількістю пофарбованих вершин, з доданком w \cdot [c_v = 0][c_u = 0].

Класична оцінка такої деревної згортки — \mathcal{O}(n^2) загалом (а не \mathcal{O}(n^3)), якщо на кожному кроці обмежувати розмір масиву фактичним розміром уже обробленої частини піддерева. При n \le 3000 це цілком проходить.

Наприкінці f(j) = \min(\mathrm{dp}[\text{корінь}][j][0],\ \mathrm{dp}[\text{корінь}][j][1]); варто ще взяти префіксні мінімуми, щоб гарантувати незростання.

Кожен запит — \mathcal{O}(\log n). Сумарна вага сягає 3000 \cdot 10^5 = 3 \cdot 10^8, тому надійніше рахувати у 64-бітному типі, а недосяжні стани позначати великою «нескінченністю».