Miền Kết Nối Tốt Nhất

Một cây có $n$ đỉnh. Mỗi đỉnh mang màu trắng hoặc đen. Một tập đỉnh được gọi là liên thông khi giữa hai đỉnh bất kỳ trong tập, toàn bộ các đỉnh trên đường đi duy nhất của chúng cũng thuộc tập.

Điểm của một tập liên thông bằng số đỉnh trắng trừ số đỉnh đen trong tập. Với mỗi đỉnh $u$, hãy tìm điểm lớn nhất của một tập liên thông có chứa $u$.

Input

• Dòng đầu chứa số nguyên $n$.

• Dòng thứ hai chứa $n$ số $c_1,c_2,\dots ,c_n$. Giá trị $1$ biểu thị đỉnh trắng, còn $0$ biểu thị đỉnh đen.

• Mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$, mô tả một cạnh vô hướng của cây.

Output

• In $n$ số nguyên trên một dòng. Số thứ $u$ là điểm lớn nhất của một tập liên thông chứa đỉnh $u$.

Constraints

• $2\le n\le 2\cdot 10^5$.
• $c_i$ thuộc $\{0,1\}$.
• $1\le u,v\le n$ và $u\ne v$.
• Các cạnh tạo thành một cây.
• Mỗi giới hạn trên áp dụng cho một test độc lập.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 15$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

2 2 2 2 1