Деревянный замок

Заметим, что существует оптимальное решение, в котором в первую очередь применяются все операции перекрашивания, а потом все операции удаления. В таком случае, ответом является количество перекрашиваний плюс количество одноцветных компонент связности после перекраски.

Обозначим за $$$0$$$ белый цвет, а за $$$1$$$ — черный. Подвесим дерево за любую вершину. Посчитаем $$$dp[i][j]$$$ — минимальное количество операций, необходимое, чтобы удалить все поддерево вершины $$$i$$$, если после перекрашиваний и до удалений она будет иметь цвет $$$j$$$. Тогда $$$dp[i][j] = \sum\limits_{u} {\min(dp[u][j] - 1, dp[u][j \oplus 1])} + cost_{i, j} + 1$$$, где вершина $$$u$$$ — сын вершины $$$i$$$ в дереве, а $$$cost_{i, j}$$$ — стоимость покраски вершины $$$i$$$ в цвет $$$j$$$ ($$$0$$$, если вершина изначально имеет цвет $$$j$$$, и $$$1$$$ иначе). В сумме для каждого сына $$$u$$$ вершины $$$i$$$ мы выбираем:

После этого, ответом на задачу будет являться $$$\min(dp[root][0], dp[root][1])$$$, где $$$root$$$ — номер вершины, являющейся корнем подвешенного дерева.