Дано дерево (связный граф без циклов) на \(n\) вершинах.
Зафиксируем число \(k\). Назовем графом \(G_k\) граф на \(n\) вершинах, в котором между вершинами \(u\) и \(v\) есть ребро тогда и только тогда, когда расстояние между вершинами \(u\) и \(v\) в данном дереве не меньше \(k\).
Для каждого \(k\) от \(1\) до \(n\) выведите количество компонент связности в графе \(G_k\).
В первой строке дано целое число \(n\) (\(2 \le n \le 10^5\)) — количество вершин в графе.
В каждой из следующих \(n-1\) строк содержатся два целых числа \(u\) и \(v\) (\(1 \le u, v \le n\)), обозначающие ребро между вершинами \(u\) и \(v\) в дереве. Гарантируется, что данные ребра задают корректное дерево.
Выведите \(n\) целых чисел — количество компонент связности в графе \(G_k\) для каждого \(k\) от \(1\) до \(n\).
В первом примере: При \(k=1\) в графе будет ребро между каждой парой вершин, поэтому в нём будет одна компонента. При \(k=4\) в графе будут только рёбра \(4 \leftrightarrow 6\) и \(5 \leftrightarrow 6\), поэтому в графе будет \(4\) компоненты.
Во втором примере: при \(k=1\) и \(k=2\) в графе одна компонента. При \(k=3\) граф \(G_k\) разбивается на \(3\) компоненты: в одной компоненте вершины \(1\), \(4\) и \(5\), а ещё две компоненты содержат по одной вершине. При \(k=4\) и \(k=5\) каждая вершина является отдельной компонентой.
6 1 2 1 3 2 4 2 5 3 6
1 1 2 4 6 6
5 1 2 2 3 3 4 3 5
1 1 3 5 5
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач