شريحة جميلة#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. ( نقاط): لا قيود إضافية.