2054. Госпиталь

В городе объявлена эпидемия волчанки. Имеющиеся госпитали не справляются с наплывом больных. Администрацией было решено вызвать эксперта по борьбе с волчанкой – Грегори Хауса. Но этот мизантроп отказывается работать в команде с кем-либо в имеющихся госпиталях и требует себе новый. Город надо спасать, поэтому его требование решено было удовлетворить и новый госпиталь построить. Теперь необходимо выбрать место, на котором он будет построен.

Город представляет из себя `n` площадей, некоторые из которых соеденены дорогами. Причём, от любой площади до любой другой можно доехать единственным способом. На `i`-й площади живёт `a_i` людей. После открытия госпиталя Хауса, наслушанные рассказами о его профессионализме, все люди пойдут в день открытия в этот госпиталь, чтобы попасть к Хаусу на осмотр. Это учитывается при выборе места строительства, и для подхода с каждой стороны будет своя дверь. К каждой двери выстроится своя очередь людей, которые подошли с этой стороны. Администрации госпиталя не хочется, чтобы людям показалось, что будут огромные очереди, и поэтому, они хотят минимизировать длину самой длинной очереди ко входу. Помогите выбрать такое место для госпиталя, чтобы самая длинная очередь была как можно короче.

В первой строке задано число площадей `n` (`1\ ≤\ n\ ≤\ 100\ 000`). Во второй строке заданы `n` чисел `a_i` (`1\ ≤\ a_i\ ≤\ 10^9`) – населённости площадей. Далее, в `n-1`-й строке, заданы номера соединённых дорогой площадей.

Выведите единственное число – номер площади, на которой можно построить госпиталь. Если ответов несколько, выведите любой.

5
3 3 2 5 1
1 2
2 3
2 4
4 5

2