Деревни лесорубов

Подвесим дерево за вершину с номером $$$1$$$. Задача решается методом динамического программирования по поддеревьям. Ответ для вершины — наибольшее количество кораблей, которое может произвести поддерево этой вершины. Рассмотрим два случая.

Если вершина $$$v$$$ не находится в подчинении ни у одного наместника, то ответ для поддерева вершины $$$v$$$ равен $$$a_v + \sum\limits_{u \in Ch_v}ans_u$$$, где $$$Ch_v$$$ — множество детей вершины $$$v$$$, а $$$ans_u$$$ — ответ для вершины $$$u$$$.

Второй случай — если в вершине $$$v$$$ находится наместник. В таком случае, ответ для вершины $$$v$$$ находится с помощью модифицированной задачи о рюкзаке. Изначально есть рюкзак вместимостью $$$|St_v| - |Ch_v|$$$, где $$$St_v$$$ — множество потомков вершины $$$v$$$, включая саму вершину $$$v$$$. Вместимость рюкзака обозначает, сколько деревень могут поставлять лес. Изначально мы знаем, что любая вершина, кроме вершин из $$$Ch_v$$$, может поставлять лес. Также, есть $$$|Ch_v|$$$ предметов. Каждый предмет можно использовать для одного из трех действий:

Такая задача решается методом динамического программирования за $$$O(|St_v| \cdot |Ch_v|)$$$. В итоге, мы получили для каждого числа $$$k$$$ от $$$0$$$ до $$$(|St_v| - |Ch_v|)$$$ максимальное количество кораблей, которое может быть суммарно построено вершинами из $$$Ch_v$$$, если ровно $$$k$$$ вершин из $$$St_v \setminus Ch_v$$$ будут поставлять лес ($$$St_v \setminus Ch_v$$$ означает множество вершин, находящихся в поддереве $$$v$$$, за исключением ее детей). Чтобы получить максимальное количество количество кораблей, которые могут суммарно построить все вершины из $$$St_v$$$ при фиксированном $$$k$$$, нужно прибавить к посчитанному значению $$$(|St_v| - |Ch_v| - k)$$$ максимальных значений $$$a_u$$$, где $$$u \in St_v \setminus Ch_v$$$. Теперь ответ для вершины — максимум посчитанных значений по всем $$$k$$$.

Ассимптотика времени работы равна:

$$$O(\sum |St_v| \cdot |Ch_v|) = O(\sum n \cdot |Ch_v|) = O(n \cdot \sum |Ch_v|) = O(n \cdot n) = O(n ^ 2)$$$.