Số màu phân biệt trong cây con

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

Với mỗi đỉnh, hãy tính số lượng màu sắc phân biệt trong cây con gốc tại đỉnh đó.

Dữ liệu vào

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

Dòng thứ hai chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$ — màu sắc của từng đỉnh.

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

Dữ liệu ra

In ra $n$ số nguyên, số thứ $i$ là số màu phân biệt trong cây con gốc tại đỉnh $i$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le c_i\le {10}^9$
• $1\le a,b\le n$

Ví dụ