Пусть \(G\) — простой граф, а \(W\) — непустое подмножество множества вершин этого графа. Назовем \(W\) почти-\(k\)-единым, если для каждой пары различных вершин \(u,v \in W\) расстояние между \(u\) и \(v\) равно либо \(k\), либо \(k+1\).
Вам задано дерево из \(n\) вершин. Для каждого \(i\) от \(1\) до \(n\) найдите максимальный размер почти-\(i\)-единого множества вершин.
В первой строке задано одно целое число \(n\) (\(2 \leq n \leq 5 \cdot 10^5\)) — количество вершин в дереве.
Затем следуют \(n-1\) строк, \(i\)-я из которых содержит два целых числа \(u_i\), \(v_i\) (\(1 \leq u_i, v_i \leq n\)), обозначающих, что существует ребро, соединяющее вершины \(u_i\) и \(v_i\).
Гарантируется, что заданный граф — дерево.
Выведите одну строку, содержащую \(n\) целых чисел \(a_i\), где \(a_i\) — максимальный размер почти-\(i\)-единого множества.
Рассмотрим первый пример.
Во втором примере существует почти-\(2\)-единое множество размера \(4\): \(\{2, 3, 5, 6\}\).
5 1 2 1 3 1 4 4 5
4 3 2 1 1
6 1 2 1 3 1 4 4 5 4 6
4 4 2 1 1 1
5000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач