Đăng và Nhật đang chơi nhảy lò cò ăn kẹo. Trò chơi được mô tả như sau:

Đăng vẽ ra trên nền nhà ~n~ ~(1 \le n \le 10^5)~ ô vuông và nối một số ô lại với nhau với ~n - 1~ đường nối. Các ô vuông tạo thành một đồ thị vô hướng có dạng cây với đỉnh gốc là ~s~. Một người đứng ở một ô vuông bất kỳ có thể nhảy từ ô này sang ô khác nếu như ô nhảy đến được kết nối với ô người đó đang đứng. Ở mỗi ô vuông, Đăng rải một số lượng kẹo nhất định. Tại ô thứ ~i~ có chứa ~k_i~ viên kẹo. Đăng đố Nhật nhảy lò cò qua các ô để lấy được số lượng kẹo là nhiều nhất.

Trò chơi bắt đầu bằng việc Nhật xuất phát ở đỉnh gốc ~s~. Khi Nhật nhảy sang một ô mới, Nhật lấy đi đúng một viên kẹo tại ô mới đến (không được phép không lấy hay lấy nhiều hơn 1). Nhật có thể di chuyển qua một ô nhiều lần. Tuy nhiên, Nhật không được phép nhảy đến một ô đã hết kẹo, và Nhật bắt buộc phải quay trở lại ô xuất phát ở đỉnh ~s~ để kết thúc trò chơi. Các bạn hãy giúp Nhật tìm số lượng kẹo nhiều nhất Nhật có thể nhặt được.

Yêu cầu:

Hãy viết chương trình tìm số lượng kẹo nhiều nhất Nhật có thể nhặt được.

Dữ liệu:

Nhập từ bàn phím gồm:

• Dòng đầu tiên chứa số nguyên dương ~n (1 \le n \le 10^5)~.
• Dòng thứ 2 chứa ~n~ số nguyên dương ~k_1, k_2, \ldots, k_n~ ~(1 \le k_i \le 10^5)~ , với ~k_i~ là số lượng kẹo tại ô thứ ~i~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~u~ và ~v~ cho biết ô thứ ~u~ được nối với ô thứ ~v~.
• Dòng cuối cùng chứa đỉnh xuất phát ~s (1 \le s \le n)~.

Kết quả:

In ra màn hình duy nhất một số nguyên là số lượng kẹo nhiều nhất Nhật có thể nhặt được.

Sample Input

6
2 1 3 5 4 6
1 2
1 3
1 4
4 5
4 6
1

Sample Output

12

Sample Input

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

Sample Output

24

Sample Input

5
1 3 1 2 3
1 4
2 4
3 5
4 5
5

Sample Output

6

Ràng buộc:

• ~20\%~ số điểm của bài tương ứng với các test có ~n \le 50, k_i \le 50~.
• ~60\%~ số điểm khác của bài tương ứng với các test có ~n \le 10^4, k_i \le 10^4~.
• ~20\%~ số điểm còn lại của bài tương ứng với các test có ~n \le 10^5, k_i \le 10^5~.