Cây có chi phí lớn nhất

Cho một cây gồm đúng $n$ đỉnh. Đỉnh thứ $v$ của cây được gán một giá trị $a_v$.

Gọi $dist(x,y)$ là khoảng cách giữa hai đỉnh $x$ và $y$, tức số cạnh trên đường đi đơn nối chúng.

Chi phí của cây được định nghĩa như sau: chọn cố định một đỉnh $v$ bất kì, khi đó chi phí bằng

$$\sum _{i=1}^{n}dist(i,v)·a_i$$

Hãy tính chi phí lớn nhất có thể của cây khi được chọn đỉnh $v$ tuỳ ý.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số đỉnh của cây.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$, trong đó $a_i$ là giá trị của đỉnh $i$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ mô tả một cạnh của cây.

Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây.

Dữ liệu ra

In ra một số nguyên duy nhất là chi phí lớn nhất có thể của cây.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le a_i\le 2·{10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$

Ví dụ