Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Почти одинаковое расстояние
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$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$$$-единого множества.

Примеры
Входные данные
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
Примечание

Рассмотрим первый пример.

  • Единственное максимальное почти-$$$1$$$-единое множество вершин — это $$$\{1, 2, 3, 4\}$$$.
  • Одно из максимальных почти-$$$2$$$-единых множеств — $$$\{2, 3, 5\}$$$, также таким множеством является $$$\{2, 3, 4\}$$$.
  • Максимальное почти-$$$3$$$-единое множество — любые две вершины на расстоянии $$$3$$$.
  • Почти-$$$k$$$-единое множество может состоять из единственной (любой) вершины для любого $$$k \geq 1$$$.

Во втором примере существует почти-$$$2$$$-единое множество размера $$$4$$$: $$$\{2, 3, 5, 6\}$$$.