Cho một đồ thị liên thông vô hướng gồm N-1 đỉnh. Với mỗi đỉnh v sẽ có một trọng số ~a_v~.

Gọi d(u, v) là khoảng cách giữa hai đỉnh u và v. Khoảng cách giữa hai đỉnh bất kỳ là số lượng cạnh trên đường đi đơn giữa chúng.

Chi phí trên cây được tính bằng tổng các tích giữa khoảng cách từ đỉnh gốc đến các đỉnh khác với trọng số của đỉnh đó.

Hay nói cách khác, nếu ta lấy một đỉnh v bất kỳ làm gốc, thì chi phí trên cây sẽ là: ~C=sum( d(v,i) * a_i),i=1..N ~.

Yêu cầu: Tìm giá trị của ~C_{max}~ là chi phí trên cây lớn nhất khi chọn một đỉnh v nào đó làm gốc.

Dữ liệu:

• Dòng đầu tiên chứa một số nguyên N (~1≤N≤2*10^5~) là số đỉnh trong cây.
• Dòng thứ hai chứa N số nguyên ~a_1, a_2, ..., a_N~ (~1≤a_i≤2*10^5~) với ~a_i~ là trọng số của đỉnh i.
• N-1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (1≤u, v≤N, u≠v) thể hiện cho một cạnh trong cây. Mỗi cặp số nguyên u, v chỉ xuất hiện một lần.

Kết quả:

Đưa ra một số nguyên duy nhất là ~C_{max}~.

Ví dụ:

Input

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

Output

121

Giải thích:

Chọn đỉnh 3 làm gốc, ta có tổng chi phí lớn nhất là: ~2*9+1*4+0*1+3*7+3*10+4*1+4*6+4*5=18+4+0+21+30+4+24+20=121~.