Священное бревно

Автор задачи: Анна Антонова, разработчик: Владислав Власов

Решим данную задачу с помощью задачи о рюкзаке. Пусть $$$\mathtt{dp}[i][j]$$$ равно true, если возможно удалить вершины суммарного веса $$$j$$$ с помощью удалений вершин $$$1, 2, \ldots, i$$$, и false иначе.

Но дальше возникают сложности — если положить вес вершины равным ее весу из условия, такое решение не учтет требование на связность оставшегося множества, а если положить вес вершины равным весу всего ее поддерева, мы можем удалить какую-то вершину больше одного раза.

Положим вес каждой вершины равным сумме исходных весов вершин в ее поддереве. Тогда задача преобразуется в подсчет $$$\mathtt{dp}[n][\mathtt{total} - w]$$$ с учетом того, что если какая-то вершина была взята в рюкзак, то никакой ее потомок не может быть взят. Чтобы учесть это, выпишем вершины в специальном порядке: перед вершиной $$$v$$$ должен идти непрерывный отрезок из всех ее потомков. Назовем массив с этим порядком $$$\mathtt{order}$$$ (на самом деле это просто развернутый Эйлеров обход дерева). Тогда положим $$$\mathtt{dp}[i][j]$$$ равным true, если можно набрать вес $$$j$$$ с помощью вершин $$$\mathtt{order}_{1, \ldots, i}$$$.

Теперь к некоторому $$$\mathtt{dp}[i][j]$$$ существует два перехода:

Если посчитать такую динамику, мы получим требуемый ответ. Время работы решения — $$$\mathcal{O}(nw)$$$.