📘 Mô tả

Cho một cây có gốc gồm n đỉnh, gốc là đỉnh 1. Mỗi đỉnh mang một màu. Với mỗi đỉnh hãy xác định số màu khác nhau xuất hiện trong toàn bộ cây con của đỉnh đó.

📥 Input

• Dòng đầu chứa một số nguyên n (1 ≤ n ≤ 2·105) — số đỉnh của cây.
• Dòng thứ hai chứa n số nguyên c1, c2, …, cn (1 ≤ ci ≤ 109) — màu của từng đỉnh.
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên a và b (1 ≤ a, b ≤ n) — mô tả một cạnh nối giữa a và b.

📤 Output

In ra n số, số thứ i là lượng màu khác nhau trong cây con gốc tại đỉnh i. Các số được in trên một dòng, cách nhau bởi một khoảng trắng.

🧪 Ví dụ

Input:

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

Output:

3 1 2 1 1

📎 Ghi chú

• Ở ví dụ trên, cây con của đỉnh 3 gồm các đỉnh 3, 4, 5 có màu 2, 2, 1 nên có 2 màu khác nhau.