- Описание
- Отправленные решения
128. Родословная: число потомков
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.
Для каждого элемента дерева определите число всех его потомков (не считая его самого).
Формат ввода
Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.
Формат вывода
Выведите список всех элементов в лексикографическом порядке, для каждого элемента выводите количество всех его потомков.
Примечание
Если вы используете рекурсию, то вам может быть полезно добавление в начало программы следующих строк:
import sys
sys.setrecursionlimit(100000)
Ограничения
Ограничение времени
2 с
Ограничение памяти
64 МБ
Пример 1
Ввод
9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I
Вывод
Alexander_I 0
Alexei 1
Anna 4
Elizabeth 0
Nicholaus_I 0
Paul_I 2
Peter_I 8
Peter_II 0
Peter_III 3