Tổng màu thống trị trên cây

Cho một cây có gốc tại đỉnh $1$, gồm $n$ đỉnh. Mỗi đỉnh được tô một màu.

Một màu $c$ được gọi là thống trị trong cây con của đỉnh $v$ nếu không có màu nào khác xuất hiện trong cây con của $v$ với số lần nhiều hơn $c$. Vì vậy có thể có nhiều hơn một màu thống trị trong cùng một cây con.

Cây con của đỉnh $v$ gồm $v$ và tất cả các đỉnh $u$ sao cho đường đi từ $u$ tới gốc đi qua $v$.

Với mỗi đỉnh $v$, hãy tính tổng tất cả các màu thống trị trong cây con của $v$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số đỉnh.
• Dòng thứ hai chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$ — màu của các đỉnh.
• Mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên $x_j,y_j$ — một cạnh của cây.

Dữ liệu ra

In ra $n$ số nguyên — tổng các màu thống trị trong cây con của từng đỉnh, theo thứ tự từ đỉnh $1$ đến $n$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le c_i\le n$
• $1\le x_j,y_j\le n$

Ví dụ