n вершин с номерами от 0 до n − 1 и корнем в вершине 0; edges[i] = [a, b] — ребро между a и b. В вершине i лежит coins[i] монет. Дано также число toll.
Монеты нужно собрать **во всех** вершинах, причём в вершине можно собирать, только когда уже собраны все её предки. Для каждой вершины выбирается один из двух способов:
- **пошлина**: получаете coins[i] − toll очков (это может быть отрицательное число);
- **половина**: получаете ⌊coins[i] / 2⌋ очков, но после этого монет в каждой вершине поддерева i становится вдвое меньше с округлением вниз.
Верните наибольшую сумму очков.edges=[[0, 1], [0, 2], [2, 3]], coins=[6, 1, 12, 9], toll=4 → 15
Вершина 0 — пошлиной: 6 − 4 = 2. Вершина 1 — пополам: 0 (пошлиной было бы −3). Вершина 2 — пошлиной: 12 − 4 = 8. Вершина 3 — пошлиной: 9 − 4 = 5. Итого 15.
edges=[[1, 0], [1, 2]], coins=[0, 8, 8], toll=3 → 7
Если взять корень 0 пополам, получим 0 вместо −3, но в вершинах 1 и 2 останется по 4 монеты, и с них выйдет лишь 2 + 2 = 4. Выгоднее заплатить пошлину в корне (−3) и в обеих вершинах (5 + 5): итого 7.
edges=[[0, 1], [0, 2], [2, 3]], coins=[6, 1, 12, 9], toll=4
15
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 52 теста на сервере, включая скрытые.