Gözəl Dilim#523

Gözəl Dilim

1,5 saniyə
256 meqabayt
Very hard

Cənab IP həyətində bir qraf tapdı. Bir az yoxladıqdan sonra, bu qrafın bir ağac olduğunu anladı! Üstəlik, hər bir zirvəyə a_i gözəllik parametri təyin edilmişdi!

O, bu ağacı otağını bəzəmək üçün istifadə etmək istəyir, lakin onu tam istifadə etmək çirkin ola biləcəyindən, onu aşağıdakıları edərək komponentlərə dilimləyəcək:

Təsəvvür edin ki, dilimdən sonra komponent qalıb.

Biz ölçüsündə bir komponentin mərkəzini zirvəsi olaraq təyin edirik ki, bu da aşağıdakı xüsusiyyəti təmin edən bütün zirvələr arasında a_v-nın ən böyük dəyərinə malikdir:

c_1, c_2, \dots, c_k qalan komponentlərin mərkəzləri olsun. Belə bir dilimin gözəlliyi a_{c_1} + a_{c_2} + \dots + a_{c_k} cəmi kimi hesablanır.

Gözəlliyi maksimum edən hər hansı bir zirvə tapın və onun əldə etdiyi gözəlliyi hesablayın!

Input

Birinci sətir bir tam ədəd (3 \le n \le 3 \cdot 10^5) — ağacdakı zirvələrin sayı.

İkinci sətir tam ədəd a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) — zirvələrin gözəllik parametrləridir.

Sonrakı n-1 sətir ağacın təsvirini ehtiva edir: i+2-ci giriş sətirində iki tam ədəd u_i və v_i (1 \le u_i, v_i \le n) — ağacın -ci kənarıdır.

Girişin etibarlı bir ağacı təsvir etdiyinə zəmanət verilir.

Output

Maksimum gözəlliyi əldə edən dilimdə istifadə olunan zirvənin indeksini və bu dilimin gözəllik dəyərini iki tam ədəd olaraq çıxarın.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Birinci nümunədə, "dilim" zirvəsinin hər seçimi üçün:

  • u = 1, iki komponentin mərkəzləri və -dür, gözəllik 2+3 = 5-dir.

  • u = 2, üç mərkəz və -dür, gözəllik 4+5+3 = 12-dir.

  • u = 3, üç mərkəz və -dir, cəmi gözəllik 6+7+2 = 15-dir.

  • u=4,5 üçün tək bir mərkəz -dür, gözəllik -dür.

  • u=6,7 üçün tək bir mərkəz -dir, gözəllik -dir.

İkinci nümunədə, zirvəsində dilimləmə edərək üç komponent yaranır: \{1\}, \{4\}, \{2,5,6\} mərkəzləri -dir və gözəllik 4+1+6=11-dir

Scoring

  1. ( xal): a_i = 1 bütün üçün;

  2. ( xal): u_i = i; v_i = i+1;

  3. ( xal): n \le 50;

  4. ( xal): n \le 10^3;

  5. ( xal): n = 2^k-1; u_i = \lfloor \frac{i+1}{2} \rfloor; v_i = i+1;

  6. ( xal): əlavə məhdudiyyət yoxdur.