📘 Mô tả

Cho một cây gồm n đỉnh, đỉnh i mang giá trị Ai. Hãy tìm một đường đi đơn sao cho tổng các giá trị trên các đỉnh thuộc đường đi đó là lớn nhất.

📥 Input

• Dòng đầu tiên chứa số nguyên n.
• Dòng thứ hai chứa n số nguyên Ai.
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v — có cạnh nối u và v.

📤 Output

In ra một số nguyên duy nhất — tổng lớn nhất tìm được.

📜 Điều kiện

• 1 ≤ n ≤ 105.
• |Ai| ≤ 109.

🧪 Ví dụ

Input:

5
1 -2 3 4 -5
1 2
2 3
3 4
4 5

Output:

7