Родословная: число потомков
Количество потомков равно сумме размеров поддеревьев детей.
Как к ней подойти
Потренируйтесь хранить пары «ключ - значение» и находить нужные записи в словаре.
Словарь связывает ключ со значением и позволяет быстро найти запись по ключу. Решите, что будет ключом, что значением и как обрабатывать отсутствующую запись. Для подсчётов удобно начинать с нуля.
Обратный порядок гарантирует, что все дети обработаны до родителя. Прибавка 1 учитывает самого ребёнка, но не текущую вершину.
Проверьте перед запуском
- В число потомков не включают саму вершину.
- У листа ответ 0.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Обратный порядок обхода
Обратный порядок гарантирует, что все дети обработаны до родителя. Прибавка 1 учитывает самого ребёнка, но не текущую вершину.
n = int(input())
parent = {}
children = {}
for _ in range(n - 1):
child, ancestor = input().split()
parent[child] = ancestor
children.setdefault(ancestor, []).append(child)
children.setdefault(child, [])
root = next(name for name in children if name not in parent)
order = [root]
for name in order:
order.extend(children[name])
count = {name: 0 for name in children}
for name in reversed(order):
if name in parent:
count[parent[name]] += count[name] + 1
for name in sorted(count):
print(name, count[name])
Время: O(n log n) из-за сортировки имён; подсчёт O(n). Память: O(n) записей и имён.
Другой способ: Увеличение счётчиков предков
Каждая вершина добавляет единицу всем своим предкам. Этот вариант нагляден, но на длинной цепочке делает квадратичное число шагов.
n = int(input())
parent = {}
children = {}
for _ in range(n - 1):
child, ancestor = input().split()
parent[child] = ancestor
children.setdefault(ancestor, []).append(child)
children.setdefault(child, [])
count = {name: 0 for name in children}
for name in children:
current = name
while current in parent:
current = parent[current]
count[current] += 1
for name in sorted(count):
print(name, count[name])
Время: O(nh + n log n), h — высота дерева. Память: O(n).