Перефразуємо задачу: пофарбувати вершину в чорний — це фактично «вилучити» її, бо ребро яскраве лише коли обидва його кінці білі. Отже, треба вибрати множину вершин мінімального розміру так, щоб сумарна вага ребер, у яких жоден кінець не належить , не перевищувала .
Оскільки запитів багато, а дерево одне, вигідно порахувати відразу всю залежність: нехай — мінімальна можлива сумарна вага яскравих ребер, якщо пофарбувати рівно вершин. Функція незростаюча, тому відповідь на запит — це найменше з f(j) \le k, яке знаходиться двійковим пошуком.
Величину рахуємо рюкзаком на дереві. Стан:
де — скільки вершин піддерева пофарбовано, а 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-бітному типі, а недосяжні стани позначати великою «нескінченністю».