29302번 - Госпиталь 스페셜 저지다국어

문제

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

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

입력

В первой строке задано число площадей $n$ (1ドル \le n \le 100{,円}000$). Во второй строке заданы $n$ чисел $a_i$ (1ドル \le a_i \le 10^9$) --- населённости площадей. Далее, в $n-1$-й строке, заданы номера соединённых дорогой площадей.

출력

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

제한

힌트