Условие:
Дима — начинающий предприниматель, мечтающий организовать лучший туристический маршрут по Якутии. Он уже составил карту, включающую N городов, соединённых двусторонними дорогами. Карта представляет собой дерево: между каждой парой городов существует единственный путь.
Каждая дорога характеризуется двумя целыми числами:
\nAᵢ — потенциальный доход, который можно получить, если включить эту дорогу в маршрут;\nBᵢ — время, необходимое для прохождения этой дороги.
Некоторые города имеют аэропорты, и маршрут должен начинаться и заканчиваться в таких городах.
Дима хочет выбрать непрерывный путь (i₁, i₂, …, iₖ) по дорогам, начинающийся и заканчивающийся в городах с аэропортами (начальный и конечный города могут совпадать), чтобы максимизировать доходность маршрута, определяемую как:
\nAᵢ₁ + Aᵢ₂ + ⋯ + Aᵢₖ\nBᵢ₁ + Bᵢ₂ + ⋯ + Bᵢₖ
.
Ваша задача — найти максимальную возможную доходность маршрута, удовлетворяющего вышеуказанным условиям.
