Bài toán

Cho một cây có ~ n ~ đỉnh gốc tại đỉnh ~ 1 ~. Mỗi đỉnh có một màu sắc. Nhiệm vụ của bạn là tính số lượng màu sắc khác nhau trong cây con của từng đỉnh.

Đầu vào

• Dòng đầu tiên chứa số nguyên ~ n ~: số lượng đỉnh (~ 1 \leq n \leq 2 \cdot 10^5 ~).
• Dòng thứ hai chứa ~ n ~ số nguyên ~ c_1, c_2, \ldots, c_n ~: màu sắc của từng đỉnh (~ 1 \leq c_i \leq 10^9 ~).
• Tiếp theo là ~ n-1 ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~: biểu diễn một cạnh giữa hai đỉnh ~ a ~ và ~ b ~.

Đầu ra

• In ra ~ n ~ số nguyên: số lượng màu sắc khác nhau trong cây con của từng đỉnh.

Kiểm tra với ví dụ

Input:

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

Output:

3 1 2 1 1

Giải thích:

• Số lượng màu sắc khác nhau trong cây con của từng đỉnh:
  • Đỉnh 1: {2, 1}.
  • Đỉnh 2: {2}.
  • Đỉnh 3: {2, 1}.
  • Đỉnh 4: {1}.
  • Đỉnh 5: {1}.