10661: Кількість різних в піддереві - 2
Відправити розв'язок
Бали:
100 (partial)
Time limit:
1.5s
Memory limit:
256M
Author:
Problem type
Allowed languages
Brain****, C, C++, Java, Pascal, Python, v8js
Задано підвішене дерево, яке містить \(N\) (\(1 \le N \le 2*10^6\)) вершин. Кожну вершину пофарбовано у один з \(N\) кольорів. Потрібно для кожної вершини \(V\) обчислити кількість різних кольорів, які зустрічаються у піддереві з коренем \(V\).
Формат вхідних даних
У першому рядку задано число \(N\). Наступні \(N\) рядків описують вершини по одній у рядку. Опис чергової вершини \(i\) має вигляд \(P\) \(C\), де \(P\) - номер батька вершини \(i\), а \(C\) - колір вершини \(i\) (\(1 \le C \le N\)). Для кореня дерева \(p\) = 0.
Формат вихідних даних
Виведіть \(N\) чисел, які позначають кількості різних кольорів у піддеревах з коренями у вершинах 1, 2, ..., \(N\).
Приклад вхідних даних-1
5
2 1
3 2
0 3
3 3
2 1Приклад вихідних даних-1
1 2 3 1 1Приклад вхідних даних-2
2
0 1
1 2Приклад вихідних даних-2
2 1
Коментарі
ура, 10 секунд