Գեղեցիկ կտոր#523

Գեղեցիկ կտոր

1,5 վայրկյան
256 մեգաբայթ
Very hard

Պարոն IP-ն իր բակում գտավ գրաֆիկ: Որոշ ստուգումներից հետո նա հասկացավ, որ այս գրաֆիկը ծառ է: Բացի այդ, յուրաքանչյուր գագաթին վերագրված էր գեղեցկության պարամետր a_i:

Նա ցանկանում է զարդարել իր սենյակը այս ծառով, բայց քանի որ ամբողջությամբ օգտագործելը կարող է անգեղձ լինել, նա կկտրի այն բաղադրիչների՝ կատարելով հետևյալը մեկ անգամ:

Անհրաժեշտ է ենթադրել, որ կտրվածքից հետո մնացել է բաղադրիչ:

Մենք սահմանում ենք կենտրոնը չափի բաղադրիչի համար որպես գագաթը, որի a_v արժեքը ամենաբարձրն է բոլոր գագաթների մեջ, որոնք բավարարում են հետևյալ հատկությանը:

Թող c_1, c_2, \dots, c_k լինեն արդյունք հանդիսացող բաղադրիչների կենտրոնները: Այդպիսի կտորի գեղեցկությունը հաշվարկվում է որպես a_{c_1} + a_{c_2} + \dots + a_{c_k}:

Գտեք ցանկացած գագաթ, որը առավելագույնի է հասցնում կտորի գեղեցկությունը, և հաշվեք, թե ինչ գեղեցկություն է այն ապահովում:

Input

Առաջին տողը պարունակում է մեկ ամբողջ թիվ (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) — ծառի -րդ եզրը:

Համոզված է, որ մուտքը նկարագրում է վավեր ծառ:

Output

Արտադրեք երկու ամբողջ թիվ և  — կտորում օգտագործված գագաթի ինդեքսը, որը ապահովում է առավելագույն գեղեցկությունը, և այդ կտորի գեղեցկության արժեքը:

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Առաջին օրինակին, յուրաքանչյուր "կտոր" գագաթի ընտրության համար.

  • 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

Scoring

  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. ( միավոր): առանց լրացուցիչ սահմանափակումների: