Задачі
Дерево
Дерево
Задано підвішене дерево, яке містить n\:(1 \le n \le 10^6) вершин. Кожну вершину пофарбовано у один з n кольорів. Потрібно для кожної вершини v обчислити кількість різних кольорів, які зустрічаються у піддереві з коренем v.
Вхідні дані
У першому рядку задано число n. Наступні n рядків описують вершини по одній у рядку. Опис чергової вершини i має вигляд p_i\:c_i, де p_i — номер батька вершини i, а c_i — колір вершини i\:(1 \le c_i \le n). Для кореня дерева p_i = 0.
Вихідні дані
Виведіть n чисел, які позначають кількості різних кольорів у піддеревах з коренями у вершинах 1, 2, ..., n.
Приклад
Вхідні дані #1
5 2 1 3 2 0 3 3 3 2 1
Вихідні дані #1
1 2 3 1 1