CF958B2.Maximum Control (medium)

The Resistance is trying to take control over as many planets of a particular solar system as possible. Princess Heidi is in charge of the fleet, and she must send ships to some planets in order to maximize the number of controlled planets.

The Galaxy contains N planets, connected by bidirectional hyperspace tunnels in such a way that there is a unique path between every pair of the planets.

A planet is controlled by the Resistance if there is a Resistance ship in its orbit, or if the planet lies on the shortest path between some two planets that have Resistance ships in their orbits.

Heidi has not yet made up her mind as to how many ships to use. Therefore, she is asking you to compute, for every K = 1, 2, 3, ..., N, the maximum number of planets that can be controlled with a fleet consisting of K ships.

抵抗组织正试图尽可能多地控制某个特定恒星系统中的行星。希迪公主负责指挥舰队，她必须向某些行星派遣飞船，以最大化所控制的行星数量。

银河系中共有 $N$ 颗行星，它们通过双向超空间隧道相互连接，且任意两颗行星之间均存在唯一路径。

若某颗行星的轨道上部署有抵抗组织的飞船，或该行星位于任意两颗已部署抵抗组织飞船的行星之间的最短路径上，则该行星即被抵抗组织所控制。

希迪尚未决定具体应部署多少艘飞船。因此，她要求你对每个 $K = 1, 2, 3, \dots, N$，计算出仅使用 $K$ 艘飞船所能控制的行星数量的最大值。

The first line of the input contains an integer N (1 ≤ N ≤ 105) – the number of planets in the galaxy.

The next N - 1 lines describe the hyperspace tunnels between the planets. Each of the N - 1 lines contains two space-separated integers u and v (1 ≤ u, v ≤ N) indicating that there is a bidirectional hyperspace tunnel between the planets u and v. It is guaranteed that every two planets are connected by a path of tunnels, and that each tunnel connects a different pair of planets.

输入的第一行包含一个整数 $N$（$1 \leq N \leq 10^5$）——表示星系中行星的数量。

接下来的 $N-1$ 行描述了行星之间的超空间隧道。每行包含两个以空格分隔的整数 $u$ 和 $v$（$1 \leq u, v \leq N$），表示行星 $u$ 与行星 $v$ 之间存在一条双向超空间隧道。保证任意两颗行星之间均存在一条隧道路径，且每条隧道连接的行星对互不相同。

On a single line, print N space-separated integers. The K-th number should correspond to the maximum number of planets that can be controlled by the Resistance using a fleet of K ships.

在一行中输出 N 个以空格分隔的整数。其中第 K 个数应表示抵抗军使用 K 艘飞船所能控制的星球的最大数量。

Consider the first example. If K = 1, then Heidi can only send one ship to some planet and control it. However, for K ≥ 2, sending ships to planets 1 and 3 will allow the Resistance to control all planets.

考虑第一个例子。如果 $K = 1$，则 Heidi 只能向某一颗行星派遣一艘飞船并控制该行星。然而，当 $K \geq 2$ 时，向行星 1 和行星 3 派遣飞船将使抵抗组织控制所有行星。