Прекрасний зріз#523

Прекрасний зріз

1,5 секунди
256 мегабайтів
Дуже складна

Містер IP знайшов граф у своєму дворі. Після огляду він зрозумів, що цей граф є деревом! Більше того, кожна вершина має параметр краси a_i!

Він хоче прикрасити свою кімнату цим деревом, але оскільки використання його цілком може бути непривабливим, він розрізає його на компоненти, виконуючи наступні дії рівно один раз:

Припустимо, що після зрізу залишилося компонент.

Ми визначаємо центроїд компоненти розміру як вершину з найбільшим значенням a_v серед усіх вершин, які задовольняють таку властивість:

Нехай 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

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі, для кожного вибору вершини "зрізу":

  • 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

Оцінювання

  1. ( балів): a_i = 1 для всіх ;

  2. ( балів): u_i = i; v_i = i+1;

  3. ( балів): n \le 50;

  4. ( балів): n \le 10^3;

  5. ( балів): n = 2^k-1; u_i = \lfloor \frac{i+1}{2} \rfloor; v_i = i+1;

  6. ( балів): без додаткових обмежень.