Містер IP знайшов граф у своєму дворі. Після огляду він зрозумів, що цей граф є деревом! Більше того, кожна вершина має параметр краси a_i!
Він хоче прикрасити свою кімнату цим деревом, але оскільки використання його цілком може бути непривабливим, він розрізає його на компоненти, виконуючи наступні дії рівно один раз:
вибрати вершину в дереві
видалити з дерева, залишаючи деякі зв'язні компоненти. Містер IP використає їх для прикраси своєї кімнати.
Припустимо, що після зрізу залишилося компонент.
Ми визначаємо центроїд компоненти розміру як вершину з найбільшим значенням a_v серед усіх вершин, які задовольняють таку властивість:
якщо видалити з компоненти, вона розпадеться на менші компоненти розміром не більше \frac{m}{2}.
Нехай c_1, c_2, \dots, c_k будуть центроїдами отриманих компонентів. Краса такого зрізу обчислюється як сума a_{c_1} + a_{c_2} + \dots + a_{c_k}.
Знайдіть будь-яку вершину , яка максимізує красу зрізу, і обчисліть красу, яку вона досягає!
Перший рядок містить одне ціле число (3 \le n \le 3 \cdot 10^5) — кількість вершин у дереві.
Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) — параметри краси вершин.
Наступні n-1 рядків містять опис дерева: i+2-ий рядок вхідних даних містить два цілі числа u_i та v_i (1 \le u_i, v_i \le n) — -е ребро дерева.
Гарантується, що вхідні дані описують дійсне дерево.
Виведіть два цілі числа та — індекс вершини, використаної в зрізі, що досягає максимальної краси, та значення краси цього зрізу.
Приклад 1
Приклад 2
У першому прикладі, для кожного вибору вершини "зрізу":
u = 1, центроїди двох компонентів та , з красою 2+3 = 5.
u = 2, три центроїди та , з красою 4+5+3 = 12.
u = 3, три центроїди та , з загальною красою 6+7+2 = 15.
Для u=4,5, єдиний центроїд з красою .
Для u=6,7, єдиний центроїд з красою .
У другому прикладі, видаляючи вершину , утворюються три компоненти: \{1\}, \{4\}, \{2,5,6\} з центроїдами та красою 4+1+6=11
( балів): a_i = 1 для всіх ;
( балів): u_i = i; v_i = i+1;
( балів): n \le 50;
( балів): n \le 10^3;
( балів): n = 2^k-1; u_i = \lfloor \frac{i+1}{2} \rfloor; v_i = i+1;
( балів): без додаткових обмежень.