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\). Ta có thể chọn nhiều đỉnh trên cây, tuy nhiên không được chọn \(2\) đỉnh kề nhau. Hỏi với cách chọn như vậy thì tổng các số lớn nhất có thể nhận được 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

6