Պարոն 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) — ծառի -րդ եզրը:
Համոզված է, որ մուտքը նկարագրում է վավեր ծառ:
Արտադրեք երկու ամբողջ թիվ և — կտորում օգտագործված գագաթի ինդեքսը, որը ապահովում է առավելագույն գեղեցկությունը, և այդ կտորի գեղեցկության արժեքը:
Example 1
Example 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;
( միավոր): առանց լրացուցիչ սահմանափակումների: