n городов с номерами от 0 до n − 1, соединённых дорогами roads так, что получается дерево: roads[i] = [a, b] — дорога между городами a и b. Посещение города i стоит cost[i].
Нужно совершить поездки из списка trips: trips[i] = [start, end] — поездка из start в end. Стоимость поездки — сумма цен всех городов на пути, включая начальный и конечный.
Перед первой поездкой можно выбрать несколько городов, **никакие два из которых не соединены дорогой напрямую**, и вдвое снизить их цены. Верните наименьшую возможную суммарную стоимость всех поездок.n=3, roads=[[0, 1], [1, 2]], cost=[4, 6, 8], trips=[[0, 2]] → 12
Поездка проходит через все три города. Скидку можно дать городам 0 и 2 (они не соседи): 2 + 6 + 4 = 12. Скидка только городу 1 дала бы 4 + 3 + 8 = 15.
n=4, roads=[[0, 1], [0, 2], [0, 3]], cost=[10, 2, 2, 2], trips=[[1, 2], [2, 3], [3, 1]] → 27
Каждая поездка идёт через центр 0, он посещается трижды. Скидка в центре: 3 · 5 + 2 · (2 + 2 + 2) = 27. Скидка во всех трёх крайних городах вместо этого дала бы 36.
n=1, roads=[], cost=[6], trips=[[0, 0], [0, 0]] → 6
n=3, roads=[[0, 1], [1, 2]], cost=[4, 6, 8], trips=[[0, 2]]
12
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 49 тестов на сервере, включая скрытые.