eolymp
Задачі

Дерево

Дерево

Задано підвішене дерево, яке містить n (1n106) вершин. Кожну вершину пофарбовано у один з n кольорів. Потрібно для кожної вершини v обчислити кількість різних кольорів, які зустрічаються у піддереві з коренем v.

Вхідні дані

У першому рядку задано число n. Наступні n рядків описують вершини по одній у рядку. Опис чергової вершини i має вигляд pi ci, де pi - номер батька вершини i, а ci - колір вершини i (1cin). Для кореня дерева pi = 0.

Вихідні дані

Виведіть n чисел, які позначають кількості різних кольорів у піддеревах з коренями у вершинах 1, 2, ..., n.

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
5
2 1
3 2
0 3
3 3
2 1
Вихідні дані #1
1 2 3 1 1
Вхідні дані #2
1
0 1
Вихідні дані #2
1
Вхідні дані #3
2
0 1
1 1
Вихідні дані #3
1 1
Вхідні дані #4
2
0 1
1 2
Вихідні дані #4
2 1
Джерело 2012 Зимняя школа Харьков, День Гольдштейна