Задачи
Дерево
Дерево
Задано подвешенное дерево, содержащее 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