Гільдія злодіїв#12955

Гільдія злодіїв (Розбір)

Зробимо двійковий пошук по відповіді. Нехай наразі потрібно перевірити, чи відповідь є не більшою за .

Будемо рахувати для вершини , чи можливо орієнтувати піддерево вершини . Для кожного сина важливо, чи ми орієнтуємо ребро від до чи навпаки.

Якщо ми орієнтуємо ребро від до , то нам важливо піддерево орієнтувати так, щоб для нього виконувалась умова, а також мінімізувати кількість монет досяжних з вершини . Назвемо таке значення 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).