Підвісимо дерево за столицю (місто ). Вартість подорожі для міста — це сума податків на шляху вгору до кореня, а президента цікавить максимум цієї величини по всіх містах.
Ключове спостереження: місто відповідає лише за деякі інцидентні йому ребра — частину ребер до дітей і, можливо, ребро до батька. Тому рішення кожного міста локальне, і задача розв'язується однією динамікою знизу вгору.
Нехай — мінімально можливий максимум вартості шляху від будь-якого міста піддерева до самого , після того як усі міста піддерева вже зробили свій вибір. Для кожного нащадка з ребром вартості c_j величина f(j) + c_j — це внесок відповідної гілки.
Тепер міркуємо, що вигідно скасувати місту . Воно може скасувати:
одне з ребер до дітей, за які воно відповідає;
або ребро до свого батька, якщо відповідає за нього.
Серед ребер до дітей має сенс скасовувати лише те, яке дає найбільший внесок серед «своїх». Якщо скасувати менше ребро, максимум визначатиметься іншою, більшою гілкою, і виграшу не буде взагалі.
Тому під час обходу дітей зручно вести дві величини: — найбільший внесок серед ребер, за які відповідає , разом із вартістю саме цього ребра, і — максимум усіх інших внесків (як чужих ребер, так і своїх, що не стали найбільшими). Якщо скасовує своє найбільше ребро, результат дорівнює
Другий варіант — скасувати ребро до батька вартістю . Тоді всередині піддерева нічого не змінюється і максимум дорівнює \max(R, D), зате батько не додасть . Найзручніше врахувати це одразу, повернувши батькові зменшене значення:
Тоді батько, як завжди, додасть вартість ребра , і вона взаємно знищиться.
Отже,
де другий варіант береться лише тоді, коли справді відповідає за ребро до батька.
Відповідь — для кореня (у нього другого варіанта немає).
Складність — : один обхід у глибину. При N \le 10^3 рекурсія безпечна. Податки не перевищують 10^4, а шлях — N-1 ребро, тому значення вміщуються у 32-бітний тип.