D. Дерево власти
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано подвешенное дерево из $$$n$$$ вершин, корнем дерева является вершина $$$1$$$. Каждая вершина имеет некоторую неотрицательную цену. Листом дерева называется вершина, не являющаяся корнем, степень которой равна $$$1$$$.

Аркадий и Василий играют в странную игру на этом дереве. Игра состоит из трех этапов. На первом этапе Аркадий покупает некоторое непустое подмножество вершин дерева. На втором этапе Василий расставляет в листьях дерева некоторые целые числа. На третьем этапе Аркадий может несколько (возможно, ни одного) раз выполнить следующую операцию: выбрать некоторую купленную на первом этапе вершину $$$v$$$ и некоторое целое число $$$x$$$, а затем прибавить ко всем числам, расставленным в листьях поддерева вершины $$$v$$$, число $$$x$$$. Число $$$x$$$ может быть положительным, отрицательным или нулем.

Лист $$$a$$$ находится в поддереве вершины $$$b$$$, если простой путь от $$$a$$$ до корня проходит через $$$b$$$.

Задача Аркадия — сделать так, чтобы числа во всех листьях оказались равными нулю. Какую минимальную сумму $$$s$$$ он должен заплатить на первом этапе, чтобы гарантировать себе победу независимо от того, как Василий расставит числа на втором этапе? Кроме этого, найдите все такие вершины, что существует оптимальный (то есть со стоимостью $$$s$$$) набор вершин, включающий заданную, купив который Аркадий может гарантировать себе победу.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — число вершин в дереве.

Вторая строка содержит $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \le c_i \le 10^9$$$), где $$$c_i$$$ — цена $$$i$$$-й вершины.

В следующих $$$n - 1$$$ строках содержатся по два целых числа $$$a$$$ и $$$b$$$ ($$$1 \le a, b \le n$$$), описывающих ребра дерева.

Выходные данные

В первой строке выведите два целых числа: минимальную стоимость $$$s$$$, которую должен заплатить Аркадий, чтобы гарантировать победу, и количество вершин $$$k$$$, которые содержатся хотя бы в одном оптимальном множестве.

Во второй строке выведите $$$k$$$ различных целых чисел в возрастающем порядке — номера вершин, которые содержатся хотя бы в одном оптимальном множестве.

Примеры
Входные данные
5
5 1 3 2 1
1 2
2 3
2 4
1 5
Выходные данные
4 3
2 4 5
Входные данные
3
1 1 1
1 2
1 3
Выходные данные
2 3
1 2 3
Примечание

Во втором примере любое множество из двух вершин является оптимальным. Поэтому каждая вершина лежит хотя бы в одном оптимальном множестве.