Ohh...
Anh như trẻ lạc còn tâm tối giữa rừng thông
Nơi cánh chim nhỏ lạc đàn tìm bến đỗ để ngừng trông
Anh là một con đom đóm mắt anh sáng đến xoay vòng
Gieo cho anh cả một mầm sống nhưng chẳng chịu công vun trồng
Vì lúc ấy ta còn trẻ nên đời bạc và mưu sinh
Anh chưa học hết lớp 10 người ta gọi là lưu linh
Anh gắn bó với sông nước và cảnh vật này hữu tình
Còn người ta cho em áo lụa hỏi tại sao chẳng phụ mình

Tình yêu ơi bình yên ơi về đây đi để anh ôm
Để gió cuốn đêm nay ai đưa về nhà để gió vang lên câu tình ca
Để lệ hoen mi khi mùa xuân đang thầm thì nhìn người mà ra đi anh chẳng níu kéo điều gì
Mà nghe sao đáng thương nhìn nhau như cố hương
Tìm em ở bốn phương vì say nên vấn vương ...
Trích Hồng Nhan Bạc Phận (J97)

Tại Bến Tre, nơi sinh ra và lớn lên của Jack97. Có một cái cây thần bí tên \(\texttt{Cây Linh Ngư}\). Đây chính là cái cây truyền thống và người dân thường dùng để biểu diễn gia phả giữa các mối quan hệ trong gia đình, dòng họ. trongphithien và p2o2HuaGiaBao đã thâm nhập được vào thánh địa của \(\texttt{Chi Điếu Hội}\) \(\text{---}\) nơi tồn tại cái cây thần bí đó. Tại đây, họ phát hiện ra một cây gia phả cổ xưa gọi là \(\texttt{Cây Linh Ngư}\), gồm \(n\) nút đại diện cho các thủ lĩnh linh hồn, kết nối với nhau bởi các nhánh kênh. Mỗi nút trên cây có một giá trị linh lực \(v_i\). Để phong ấn toàn bộ Chi Điếu Hội, họ cần chọn ra một tập hợp các nút sao cho không có hai nút nào được chọn mà lại có mối quan hệ cha-con trực tiếp (tập độc lập), đồng thời tổng linh lực của các nút được chọn phải là lớn nhất.
Yêu cầu: Cho một cây có \(n\) nút, mỗi nút có giá trị \(v_i\). Hãy tìm tập độc lập có tổng giá trị các nút lớn nhất.

Input

• Dòng đầu: số nguyên \(n\) (\(2 \le n \le 2 \cdot 10^5\)).
• Dòng hai: \(n\) số nguyên \(v_i\) (\(|v_i| \le 10^9\)).
• \(n-1\) dòng tiếp theo: Mỗi dòng gồm \(u, v\) thể hiện một cạnh nối giữa hai nút.

Output

• In ra giá trị tổng linh lực lớn nhất tìm được.

Example

5
10 20 30 40 50
1 2
1 3
2 4
2 5

120

3
657168938 -230210953 -95301331
2 1
3 2

657168938