Зробимо двійковий пошук по відповіді. Нехай наразі потрібно перевірити, чи відповідь є не більшою за .
Будемо рахувати для вершини , чи можливо орієнтувати піддерево вершини . Для кожного сина важливо, чи ми орієнтуємо ребро від до чи навпаки.
Якщо ми орієнтуємо ребро від до , то нам важливо піддерево орієнтувати так, щоб для нього виконувалась умова, а також мінімізувати кількість монет досяжних з вершини . Назвемо таке значення down_{to}.
Якщо ми орієнтуємо ребро від до , то також потрібно, виконувалась умова, а також мінімізувати найбільшу кількість монет досяжних з певної вершини, з якої також досяжна вершина . Назвемо таке значення up_{to}.
Нехай – це множина синів вершини таких, що ми орієнтуємо ребро від неї до , - множина синів, де ми орієнтуємо ребро до сина.
Тоді нам потрібно розбити на множини так, щоб max_{to \in A} up_{to} + \sum_{to \in B} down_{to} + a_v \le x.
Якщо посортувати всіх синів по значенню , то вигідно деякий префікс взяти в множину і суфікс в множину . Так ми зможемо перевірити, чи все ще виконується умова. Залишилось перерахувати значення up_v та down_v.
up_v - мінімальне можливе значення max_{to \in A} up_{to} + \sum_{to \in B} down_{to} + a_v.
down_v - мінімальне можливе значення \sum_{to \in B} down_{to} + a_v, серед таких, що задовольняють умову.
Тож обидва ці значення можна порахувати разом з перевіркою умови двійкового пошуку.
Складність розв’язку O(n \log^2 n).