Trong khu vườn quốc gia có \(N\) địa điểm, giữa các địa điểm có đường mòn đi bộ tạo thành cấu trúc cây. Mỗi địa điểm i được đánh giá với một giá trị tham quan \(a_i\) (có thể âm nếu địa điểm đó nguy hiểm).

Một nhóm khách du lịch muốn đi theo một đường đi đơn (mỗi địa điểm chỉ đi qua một lần) sao cho tổng giá trị tham quan của các địa điểm trên đường đi là lớn nhất.

\(|1| \le 20\) | 10 | \(|2| \le 5000\) | 20 | \(|3| \le 2 \cdot 10^5\) | 30 | \(|4| \le 2 \cdot 10^5\) | 40 |

Đầu vào:

• Dòng đầu gồm \(N\).
• Dòng thứ hai gồm \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(|a_i| \le 10^9\)). - N - \(1\) dòng sau, mỗi dòng gồm \(u, v\).

Đầu ra:

• Một số nguyên là tổng lớn nhất tìm được.

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) là trọng số các đỉnh (\(|a_i| \le 10^9\)). - N-\(1\) dòng tiếp theo: mỗi dòng chứa 2 số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra tổng trọng số đỉnh lớn nhất trên một đường đi đơn trên cây.

Ví dụ

Input:

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

Output:

8

Giải thích: Đường đi tối ưu là 1 -> 3 -> 4 có tổng trọng số \(1 + 3 + 4 = 8\).

Ràng buộc & Subtasks