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:
ağacda bir zirvə seçin
-nu ağacdan çıxarın, bəzi bağlı komponentlər buraxın. Cənab IP bunları otağını bəzəmək üçün istifadə edə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:
əgər komponentdən çıxarılarsa, o, ən çox \frac{m}{2} ölçüsündə daha kiçik komponentlərə parçalanır.
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!
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.
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.
Example 1
Example 2
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
( xal): a_i = 1 bütün üçün;
( xal): u_i = i; v_i = i+1;
( xal): n \le 50;
( xal): n \le 10^3;
( xal): n = 2^k-1; u_i = \lfloor \frac{i+1}{2} \rfloor; v_i = i+1;
( xal): əlavə məhdudiyyət yoxdur.