n посёлков с номерами от 0 до n - 1, соединённых n - 1 двусторонними дорогами так, что из любого посёлка можно доехать в любой другой (то есть дороги образуют дерево). Дорога roads[i] = [a, b] соединяет посёлки a и b. В массиве coins для каждого посёлка записано 1, если в нём лежит монета, и 0, если нет.
Курьер выбирает любой посёлок как стартовый. Дальше он сколько угодно раз делает одно из двух:
- забирает все монеты из посёлков, до которых от текущего не больше двух дорог;
- проезжает по одной дороге в соседний посёлок.
Нужно собрать все монеты и вернуться в стартовый посёлок. Верните наименьшее число проездов по дорогам; если по одной дороге проехать несколько раз, считается каждый проезд.coins=[1, 0, 0, 0, 0, 0, 1], roads=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]] → 4
Встаём в посёлок 2 и подбираем монету из посёлка 0 (до него две дороги). Едем в 3, потом в 4 — оттуда достаём монету в 6. Возвращаемся 4 → 3 → 2: всего 4 проезда.
coins=[0, 1, 0, 1, 0], roads=[[0, 1], [0, 2], [0, 3], [3, 4]] → 0
Из посёлка 0 обе монеты (в 1 и в 3) на расстоянии одной дороги — никуда ехать не нужно.
coins=[0, 0, 0], roads=[[0, 1], [1, 2]] → 0
coins=[1, 0, 0, 0, 0, 0, 1], roads=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]
4
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 59 тестов на сервере, включая скрытые.