Bạn được cho một cây gốc (rooted tree) với đỉnh gốc là đỉnh số 1. Mỗi đỉnh trong cây được tô một màu nào đó. Chúng ta gọi màu \(c\) là màu 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 nhiều hơn màu \(c\) trong cây con của đỉnh \(v\). 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 một đỉnh \(v\) bao gồm: Chính đỉnh \(v\), và Tất cả các đỉnh khác nằm phía dưới \(v\) trong cây (nghĩa là: mọi đỉnh mà đường đi từ nó đến gốc đều đi qua \(v\)).

Nhiệm vụ của bạn: 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 đỉnh đó.

Dữ liệu vào:

+ Dòng đầu tiên chứa một số nguyên \(n\ (1\ \leq \ n\ \leq \ 10⁵)\) — số lượng đỉnh trong cây.

+ Dòng thứ hai chứa \(n\) số nguyên \(c₁,\ c₂,\ ...,\ cₙ\) \((1\ \leq \ cᵢ\ \leq \ n)\), trong đó \(cᵢ\) là màu của đỉnh thứ \(i\).

+ Mỗi dòng tiếp theo trong số \(n\ - \ 1\) dòng tiếp theo chứa hai số nguyên \(xⱼ\) và \(yⱼ\) \((1\ \leq \ xⱼ,\ yⱼ\ \leq \ n)\), biểu diễn một cạnh của cây (nối đỉnh \(xⱼ\) với \(yⱼ\)).

Kết quả:

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

Ví dụ: