Trọng số đường đi

Cho đồ thị liên thông gồm ~n~ đỉnh và ~n - 1~ cạnh. Đỉnh thứ ~i~ có trọng số ~c_i~. Ký hiệu ~len(u, v)~ là số cạnh đi qua trên đường đi từ ~u~ đến ~v~ sao cho không có cạnh nào được đi qua quá một lần. Dễ thấy với mỗi cặp ~(u, v)~ ~(1 \le u, v \le n)~ bất kỳ, đường đi từ ~u~ đến ~v~ này luôn là duy nhất.

Ta ký hiệu ~g(u, v)~ là trọng số của một đường đi từ ~u~ đến ~v~ được tính bằng công thức:

~g(u, v) = len(u, v) \times \min(c_u, c_v).~

Yêu cầu

Xác định đường đi có trọng số lớn nhất trong đồ thị.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~c_1, c_2, \ldots, c_n~ ~(c_i \le 10^9, \forall i = 1, 2, 3, \ldots, n)~.
• ~n - 1~ dòng cuối cùng, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i~ xác định cạnh nối trực tiếp giữa ~u_i~ và ~v_i~ ~(1 \le u_i, v_i \le n)~.

Kết quả

Ghi một số nguyên duy nhất là trọng số của đường đi có trọng số lớn nhất tìm được.

Ví dụ

Dữ liệu vào

6
5 9 8 7 10 2
1 2
1 6
2 5
3 5
2 4

Kết quả

21

Ràng buộc

• Có ~10/30~ số test có ~u_i = i, v_i = i + 1~, ~\forall i = 1, \ldots, n - 1~; ~n \le 100~.
• Có ~5/30~ số test khác có ~n \le 100~.
• Có ~5/30~ số test khác có ~n \le 4000~.
• Có ~10/30~ số test còn lại không có ràng buộc gì thêm.