В одному королівстві є міст, з’єднаних n-1 дорогою так, що між кожною парою міст можливо добратись дорогами. Іншими словами, міста та дороги утворюють дерево.
У кожному місті є банк, в сховищі банку в місті знаходиться a_v монет. В одному з міст зародилась гільдія злодіїв, яка планує пограбувати банки усього королівства. На жаль, король не знає в якому саме місті це сталось, тож для протидії великого пограбування він вирішив зробити усі дороги королівства односторонніми, попри те, що після цього уже неможливо дістатись з будь-якого міста в будь-яке інше.
Та все ж, пограбування відбудеться! Гільдія пограбує усі банки в усіх містах, в які можливо добратись від міста, де гільдія зародилась.
Король хоче обрати такі напрямки доріг, щоб мінімізувати максимальний можливий збиток. Більш формально, нехай c_v – сума кількості монет у всіх містах, які досяжні з міста після того, як король обере напрямок кожної дороги (включно з містом ). Тоді вам потрібно обрати напрямки так, щоб мінімізувати \max c_v.
В першому рядку задано єдине ціле число – кількість міст королівства.
У наступному рядку задано цілих чисел a_i – кількість монет у банках.
-ий з наступних n-1 рядків містить два цілі числа u_i та v_i, що означає, що між містами з цими номерами є дорога.
2 \le n \le 10^5,
1 \le a_i \le 10^9,
1 \le u_i, v_i \le n.
Виведіть єдине число – мінімальне можливе значення \max c_v.
Example
Example 1
Example 2
У першому приклад у вершині знаходиться монет. Можлива орієнтація ребер зображена на рисунку. Тоді якщо гільдія розташована у вершині 2, а отже вони можуть пограбувати банк у вершинах 1, 2, 4 та 5. c_2 = a_1 + a_2 + a_4 + a_5 = 12. Для всіх інших вершин це значення є меншим.
Перший приклад.
У другому прикладі у кожній вершині по одній монеті. Один з варіантів, як орієнтувати ребра:
Другий приклад.