CF1039D.You Are Given a Tree

A tree is an undirected graph with exactly one simple path between each pair of vertices. We call a set of simple paths $k$-valid if each vertex of the tree belongs to no more than one of these paths (including endpoints) and each path consists of exactly $k$ vertices.

You are given a tree with $n$ vertices. For each $k$ from $1$ to $n$ inclusive find what is the maximum possible size of a $k$-valid set of simple paths.

树是任意两个顶点之间恰好存在一条简单路径的无向图。我们称一组简单路径为 $k$-合法 的，当且仅当：树中的每个顶点至多属于其中一条路径（端点也计入），且每条路径恰好包含 $k$ 个顶点。

给定一棵含 $n$ 个顶点的树。对每个从 $1$ 到 $n$（含）的 $k$，求 $k$-合法的简单路径集合的最大可能大小。

The first line of the input contains a single integer $n$ ($2 \le n \le 100\,000$) — the number of vertices in the tree.

Then following $n - 1$ lines describe the tree, each of them contains two integers $v$, $u$ ($1 \le v, u \le n$) — endpoints of the corresponding edge.

It is guaranteed, that the given graph is a tree.

输入的第一行包含一个整数 $n$（$2 \le n \le 100\,000$）——树中顶点的数量。

接下来的 $n - 1$ 行描述该树，每行包含两个整数 $v$、$u$（$1 \le v, u \le n$）——对应边的两个端点。

保证给定的图是一棵树。

Output $n$ numbers, the $i$-th of which is the maximum possible number of paths in an $i$-valid set of paths.

输出 $n$ 个数，其中第 $i$ 个数表示一个 $i$-合法路径集合中可能包含的路径的最大数目。

One way to achieve the optimal number of paths for the second sample is illustrated in the following picture:

实现第二个样例的最优路径数的一种方法如下图所示：