Максимальна сума на дереві (Розбір)

Нехай $v$ — вершина дерева. Позначимо через:

• $d{p}_1(v)$ найбільшу суму монет, яку можна зібрати з піддерева з коренем $v$, якщо монети у вершині $v$ ми беремо.

• dp_2(v) найбільшу суму монет, яку можна зібрати з піддерева з коренем $v$, якщо монети у вершині $v$ ми не беремо.

Тоді відповіддю на задачу буде max(dp_1(1), dp_2(1)), якщо взяти першу вершину за корінь дерева.

Визначимо рекурсивно наведені функції:

• Якщо монети у вершині $v$ ми беремо, то брати монети з її синів не можна: