Cho đồ thị dạng cây \(T[1]\), gồm \(N\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(N\), mỗi đỉnh \(i\) được gán một số nguyên dương \(a_i\), hỏi đường đi có tổng các số ghi trên các đỉnh từ gốc cây xuống một đỉnh bất kì là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên là số \(N\) là số đỉnh của đồ thị.
• Dòng tiếp theo ghi \(N\) số nguyên dương \(a_1, a_2, a_3... a_N\) là các số được gán với \(N\) đỉnh theo thứ tự.
• \(N-1\) dòng tiếp theo, mỗi dòng có 2 số \(u\) và \(v\) là cạnh nối đỉnh \(u\) đến \(v\).

Dữ liệu ra

• Một số duy nhất là đường đi có tổng lớn nhất.

Ràng buộc

• \(N \le 2 \times 10^5\)
• \(a_i \le 10^9\)

Input 1

4
4 2 2 1
1 3
2 3
2 4

Output 1

9