Автор задачи: Даниил Голов, разработчики: Даниил Голов и Даниил Орешников
Переформулируем задачу чуть более коротко: дано подвешенное дерево, и требуется «пометить» (назначить мнение A) некоторое количество вершин, чтобы количество ребер, на которых верхняя вершина помечена, а нижняя — нет, было максимально.
Эта задача всем в своем условии намекает на динамическое программирование по поддеревьям, более того, она очень похожа на задачу о максимальном независимом множестве на дереве, которая также решается с помощью динамики. В этой задаче мы заведем такие же состояния:
Для начала найдем максимальное возможное значение беспорядка, которое мы можем получить, а затем восстановим, какие вершины для этого надо было пометить. Для этого считаем все связи из ввода и сделаем обход в глубину из вершины номер $$$1$$$ — так мы сможем определить для каждого ребра, какая вершина является родителем («ментором»), а какая — ребенком («подчиненным»).
Теперь (можно и на выходе из dfs) будем считать значения динамики. Заметим, что если мы зафиксируем, помечена ли вершина, дальше можно оптимизировать поддеревья ее детей независимо: действительно, от изменений в одном поддереве значения беспорядка в других не изменятся. Рассмотрим оба варианта: и когда $$$v$$$ не помечена, и когда помечена.
Здесь хороший момент, чтобы вспомнить, что нас еще просят восстановить, какие вершины должны быть помечены, а какие — нет. Воспользуемся стандартной техникой для восстановления ответа: запомним, какой выбор привел нас к максимальному значению. А именно, заведем $$$\mathtt{down}[v][0]$$$ и $$$\mathtt{down}[v][1]$$$, которые будут содержать номера всех детей $$$v$$$, которые должны быть помечены, чтобы $$$\mathtt{dp}[v][0]$$$ и $$$\mathtt{dp}[v][1]$$$, соответственно, были максимальны.
Для их заполнения в формулах пересчета $$$\mathtt{dp}$$$ вместо того, чтобы просто брать максимум из двух опций, посмотрим, какая из них больше, и отметим соответствующую информацию в $$$\mathtt{down}$$$. Так, если $$$\mathtt{dp}[u_i][0] + 1 < \mathtt{dp}[u_i][1]$$$, добавим $$$u_i$$$ в $$$\mathtt{down}[v][1]$$$, так как его выгоднее пометить, чем не помечать.
После того, как все вершины будут обработаны, максимальное значение беспорядка можно получить как $$$\max(\mathtt{dp}[1][0], \mathtt{dp}[1][1])$$$. Более того, зная, какая из двух этих величин больше, мы знаем, стоит ли отмечать вершину $$$1$$$, чтобы достичь такого значения беспорядка. Запомним эту информацию, и спустимся по дереву: если очередной $$$u_i$$$ лежит в соответствующем выбранному для первой вершины состоянию $$$\mathtt{down}[1]$$$, то $$$u_i$$$ тоже надо пометить, иначе — не надо. Так продолжаем спускаться по дереву, каждый раз восстанавливая состояния вершин.
Суммарно на подсчет такой динамики и спуск по дереву мы потратили время, пропорциональное количеству ребер в графе (по каждому ребру мы прошли константное число раз), поэтому весь этот алгоритм работает за $$$\mathcal{O}(n)$$$