Задача №113337. Поздний контест
Много в мире разных часовых поясов! Именно поэтому соревнования по программированию часто бывают в неудобное для некоторых людей время. Как-то раз Гриша и Егор решили поучавствовать в соревновании, которое заканчивалось очень поздно. Именно поэтому ребята решили переночевать в гостинице, чтобы не возвращаться домой поздно. Однако все не так просто. Родители Егора и Гриши очень волнуются за своих детей, поэтому они решили установить по всему городу камеры, чтобы видеть, где находятся ребята.
В городе, где живут программисты 1 ≤ n ≤ 500 000 перекрестков, соединенных n - 1 дорогой так, что между любыми двумя перекрестками существует путь по дорогам.
Родители собираются установить на перекрестках города камеры, радиус действия которых равен длине дороги. Родители будут спокойны, если смогут видеть ребят на любой дороге и на любом про перекрестке. Иными словами, для каждого перекрестка должен существовать перекресток, находящийся на расстоянии не более одной дороги, такой что на нем установлена камера и для любой дороги должна быть установлена камера хотя бы на одном конце этой дороги. Установка камер — затратное дело, поэтому для каждого перекрестка с номером i известна стоимость 1 ≤ cost i ≤ 10 9 установки камеры на нем.
Помогите родителям установить камеры надлежащим образом за минимальную стоимость.
В первой строке входного файла содержится количество перекрестков n ( 1 ≤ n ≤ 500 000 ).
В последующих n - 1 строках содержатся v i u i — перекрестки соединенные очередной дорогой.
Последняя строчка входного файла содержит n чисел сost 1 , сost 2 , ..., сost n ( 1 ≤ сost i ≤ 10 9 ) — стоимости установки камер на перекрестках.
В первой строке выведете минимальную стоимость установки ans и количество перекрестков k , в которых надо установить камеры.
Во второй строке выведите k чисел — перекрестки, в которых надо установить камеры.
Если ответов несколько, разрешается вывести любой из них.
6 1 2 2 3 1 4 4 5 4 6 228 1488 2 2 8 1
232 3 1 3 4