Автори задачі: | Фейса Богдан, Тимкович Олександр |
Задачу підготував: | Фейса Богдан |
Розбір написав: | Фейса Богдан |
На повний бал задача розв'язується за допомогою динамічного програмування по дереву.
Нехай dp[v][0] відповідає за мінімальну кількість вершин з піддерева , які нам потрібно взяти для того, щоб кожна іграшка в піддереві була приєднана до якоїсь іншої іграшки з цього ж піддерева.
Також нехай dp[v][1] відповідає за мінімальну кількість вершин з піддерева , які нам потрібно взяти для того, щоб якась іграшка в піддереві не була приєднана до якоїсь іншої іграшки з цього ж піддерева і її потрібно було спарувати з якоюсь іграшкою поза цим піддеревом.
Тоді, для листків нашого дерева значення будуть наступні:
Для вершини визначимо наступні значення:
сума мінімальних значень для піддерев вершини, якщо для кожної дитини дозволено вибрати лише
сума мінімальних значень для піддерев вершини, якщо для кожної дитини дозволено вибрати dp[i][0] \text{ або } dp[i][1] \text{ але як мінімум один раз вибирається } dp[i][1]
сума мінімальних значень для піддерев вершини, якщо для кожної дитини дозволено вибрати dp[i][0] \text{ або } dp[i][1] \text{ але як мінімум 2 рази вибирається } dp[i][1]
Для того, щоб визначати переходи, розіб'ємо все на 2 випадки:
Якщо в вершині міститься іграшка, то переходи наступні:
Якщо ж іграшки нема, то переходи наступні:
Всі ці значення можна обрахувати за сумарний час .