409738: GYM103714 H Еловый городок
Description
Городок Еловый славится своими двумя вещами — здесь каждую неделю Новый год и везде очень узкие дороги. Если с первым еще можно как-то бороться, то со вторым городу очень тяжело. Именно поэтому жителям нужна Ваша помощь!
Вам дана карта города Еловый. Как ни странно, он очень похож по форме на елку. Елью в данной задаче будем называть неориентированный граф, состоящий из цикла, к которому присоединён черенок, представляющий собой несколько последовательно связанных рёбер. Самую отдалённую от цикла вершину черенка будем называть корнем ели. В корне находится выезд из города. На некоторых улицах города с последнего Нового года лежат ёлки, которые надо вывезти из города.
Необходимо помочь уборочной машине убрать все елки из городка, пока не наступил Новый год! Ведь начинать новую неделю Нового года со старой елкой является плохой приметой в этом городе. Вы можете выбрать любую вершину графа в качестве стартовой точки, но главным условием является закончить сбор елок на выезде из города, иначе елки вывезти не удастся, ведь разворачиваться на узкой дороге нельзя, не правда ли? Так же, вы не можете посещать одну вершину несколько раз — мэр города, который построил такие дороги точно уверен, что есть более оптимальный маршрут для сбора елок!
Елки ждут!
Входные данныеПервая строка входных данных содержит одно целое число $$$n$$$ ($$$4 \le n \le 10^3$$$) — количество вершин в ёлке.
Во второй строке входных данных содержится $$$n$$$ целых чисел $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) — количество ёлок в каждой вершине.
В следующих $$$n$$$ строках содержится по два целых числа $$$v$$$, $$$u$$$ ($$$1 \le v, u, \le n, v \ne u$$$), описывающих ребро между вершинами $$$v$$$ и $$$u$$$. Между каждой парой вершин существует не более одного ребра.
Гарантируется, что рёбра задают ёлку — граф, состоящий из цикла, к которому присоединены несколько последовательно связанных рёбер.
Выходные данныеВыведите длину кратчайшего пути, пройдя по которому, можно собрать все ёлки.
ПримерыВходные данные5 0 0 0 0 18 1 2 2 3 3 4 4 5 5 2Выходные данные
2Входные данные
4 3 1 6 3 4 1 1 2 2 4 2 3Выходные данные
3Примечание
Графическое представление примера показано на рисунке $$$1$$$.