Финал кок-бору
Кок-бору — древняя конная игра кочевников и главный вид программы Всемирных игр кочевников. Федерация кок-бору Кыргызстана готовит национальный чемпионат: в каждом из n сёл есть своя команда, а сёла соединены n − 1 дорогами так, что между любыми двумя сёлами есть ровно один путь (дороги образуют дерево).
Каждая пара команд сыграет между собой один матч. Расстоянием между сёлами назовём количество дорог на пути между ними: столько дней гостям нужно добираться верхом с табуном. Чтобы спланировать расходы на переезды, федерации нужна таблица: для каждого k от 1 до n − 1 — сколько пар сёл находятся на расстоянии ровно k.
Входные данные
В первой строке — целое число n (1 ≤ n ≤ 200 000).
В каждой из следующих n − 1 строк — два числа a и b (1 ≤ a, b ≤ n): дорога между сёлами a и b. Гарантируется, что дороги образуют дерево.
Выходные данные
Выведите в одной строке n − 1 чисел: k-е число — количество неупорядоченных пар сёл на расстоянии k. Если n = 1, выведите пустую строку.
Пример 1
Вход:
6
1 2
2 3
2 4
4 5
4 6
Выход:
5 6 4 0 0
Пояснение
На расстоянии 1 находятся 5 пар (по одной на каждую дорогу), на расстоянии 2 — пары 1–3, 1–4, 3–4, 2–5, 2–6, 5–6, на расстоянии 3 — пары 1–5, 1–6, 3–5, 3–6. Сёл на расстоянии 4 и 5 нет.
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 10 | n ≤ 3000 |
| 2 | 20 | дороги соединяют сёла i и i + 1 |
| 3 | 20 | n ≤ 20 000 |
| 4 | 50 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Примечание
Ответы могут превышать 2³¹ — используйте 64-битные целые числа.
Комментарии
import sys
Настройка лимита рекурсии для глубоких деревьев
sys.setrecursionlimit(300000)
def solve():
if __name__ == '__main__': solve()