Родословная: число потомков
Вы решили задачу. Теперь можно сравнить подходы.
Количество потомков равно сумме размеров поддеревьев детей.
Авторский разбор для локальной версии на основе условия задачи. Это не выгрузка чужих посылок и не официальное решение исходного сайта.
Ваше принятое решение
Рекомендуемое решение: Обратный порядок обхода
Обратный порядок гарантирует, что все дети обработаны до родителя. Прибавка 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).
На что обратить внимание
- В число потомков не включают саму вершину.
- У листа ответ 0.
Рекомендация учитывает сложность и читаемость для этой задачи. Единственного самого быстрого решения для всех размеров входа и всех компьютеров может не быть.