Sakurako and a Falling Tree #367

Sakurako and a Falling Tree (Editorial)

Автори задачі:

Фейса Богдан, Тимкович Олександр

Задачу підготував:

Фейса Богдан

Розбір написав:

Фейса Богдан

На повний бал задача розв'язується за допомогою динамічного програмування по дереву.

Нехай dp[v][0] відповідає за мінімальну кількість вершин з піддерева , які нам потрібно взяти для того, щоб кожна іграшка в піддереві була приєднана до якоїсь іншої іграшки з цього ж піддерева.

Також нехай dp[v][1] відповідає за мінімальну кількість вершин з піддерева , які нам потрібно взяти для того, щоб якась іграшка в піддереві не була приєднана до якоїсь іншої іграшки з цього ж піддерева і її потрібно було спарувати з якоюсь іграшкою поза цим піддеревом.

Тоді, для листків нашого дерева значення будуть наступні:

dp[v][0]=\begin{cases}INF, \text{якщо в листку знаходиться іграшка}\\ 0, \text{якщо листок порожній }\end{cases}
dp[v][1]=\begin{cases}1, \text{якщо в листку знаходиться іграшка}\\ INF, \text{якщо листок порожній }\end{cases}

Для вершини визначимо наступні значення:

сума мінімальних значень для піддерев вершини, якщо для кожної дитини дозволено вибрати лише

сума мінімальних значень для піддерев вершини, якщо для кожної дитини дозволено вибрати dp[i][0] \text{ або } dp[i][1] \text{ але як мінімум один раз вибирається } dp[i][1]

сума мінімальних значень для піддерев вершини, якщо для кожної дитини дозволено вибрати dp[i][0] \text{ або } dp[i][1] \text{ але як мінімум 2 рази вибирається } dp[i][1]

Для того, щоб визначати переходи, розіб'ємо все на 2 випадки:

Якщо в вершині міститься іграшка, то переходи наступні:

dp[v][0]=mn1+1
dp[v][1]=min(mn1,mn)+1

Якщо ж іграшки нема, то переходи наступні:

dp[v][1]=mn1+1
dp[v][0]=min(mn2+1,mn)

Всі ці значення можна обрахувати за сумарний час .