Cerința

Avem în cartier un arbore cu nodurile colorate și cu rădăcina nodul 1. Pentru fiecare nod i al arborelui să se afișeze câte culori distincte sunt în subarborele cu rădăcina în i.

Date de intrare

Programul citește de la tastatură numărul n, reprezentând numărul de noduri al arborelui. Pe a doua linie se vor afla n valori, cea de a i reprezentând culoarea nodului i. Urmează n-1 linii, pe fiecare linie aflânduse 2 numere a b indicând faptul ca între a și b este muchie.

Date de ieșire

Programul va afișa pe ecran n numere, cel de al i-lea fiind numărul de culori distincte din subarborele cu rădăcina în i.

Restricții și precizări

• 1 ≤ n ≤ 200.000
• Culorile arborelui sunt numere naturale mai mici sau egale cu 1.000.000.000

Exemplu:

Intrare

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

Ieșire

3 1 2 1 1