e-olymp
Yarışlar

IOI Preparation - Trees

Дерево

Задано подвешенное дерево, содержащее n (1n106) вершин. Каждая вершина покрашена в один из n цветов. Требуется для каждой вершины v вычислить количество различных цветов, встречающихся в поддереве с корнем v.

Входные данные

В первой строке задано число n. Следующие n строк описывают вершины по одной в строке. Описание очередной вершины i имеет вид pi ci, где pi - номер родителя вершины i, а ci - цвет вершины i (1cin). Для корня дерева pi = 0.

Выходные данные

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

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
5
2 1
3 2
0 3
3 3
2 1
Çıxış verilənləri #1
1 2 3 1 1
Giriş verilənləri #2
1
0 1
Çıxış verilənləri #2
1
Giriş verilənləri #3
2
0 1
1 1
Çıxış verilənləri #3
1 1
Giriş verilənləri #4
2
0 1
1 2
Çıxış verilənləri #4
2 1
Mənbə 2012 Зимняя школа Харьков, День Гольдштейна