Деревом называется связный неориентированный граф, в котором между любыми двумя вершинами существует ровно один простой путь. Будем говорить, что множество простых путей является \(k\)-допустимым, если каждая вершина дерева принадлежит не более чем одному из этих путей (включая концевые вершины) и каждый путь состоит ровно из \(k\) вершин.
Вам дано дерево на \(n\) вершинах. Для каждого \(k\) от \(1\) до \(n\) включительно найдите максимально возможную мощность \(k\)-допустимого множества простых путей.
Первая строка содержит одно целое число \(n\) (\(2 \le n \le 100\,000\)) — количество вершин в дереве.
Следующие \(n - 1\) строк задают дерево, каждая из них содержит два целых числа \(v\) и \(u\) (\(1 \le v, u \le n\)) — концы соответствующего ребра.
Гарантируется, что заданный граф является деревом.
Выведите \(n\) чисел, \(i\)-е из которых равно максимально возможной мощности \(i\)-допустимого множества путей.
Один из способов достичь наибольшего количества путей во втором примере изображён на следующей картинке:
7 1 2 2 3 3 4 4 5 5 6 6 7
7 3 2 1 1 1 1
6 1 2 2 3 2 4 1 5 5 6
6 2 2 1 1 0
7000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач