CF2165E.Rainbow Branch

Given a tree with $n$ vertices, you need to assign a color to each edge. Define the inconvenience of an assignment as the maximum number of colors on the path between any two vertices.

You need to assign exactly $k$ different colors (each color must appear at least once) to the edges while minimizing the inconvenience of the assignment.

Please calculate the minimum inconvenience for all $k=1,2,\ldots,n-1$.

给定一棵包含 $n$ 个顶点的树，你需要为每条边分配一种颜色。定义一个染色方案的不便度（inconvenience）为任意两个顶点之间路径上所出现的不同颜色数的最大值。

你需要恰好使用 $k$ 种不同的颜色（每种颜色至少出现一次）为所有边染色，并使该染色方案的不便度最小化。

请对所有 $k = 1, 2, \ldots, n-1$，计算对应的最小不便度。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of the input contains one positive integer $n$ ($3\le n\le3\cdot10^5$) — the number of vertices.

The next $n-1$ lines each contain two positive integers $u_i,v_i$ ($1\le u_i,v_i\le n$) — indicating that there is an edge between vertices $u_i$ and $v_i$.

It is guaranteed that the edges in the input form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

输入的第一行包含一个正整数 $n$（$3\le n\le3\cdot10^5$）—— 表示顶点的数量。

接下来的 $n-1$ 行每行包含两个正整数 $u_i, v_i$（$1\le u_i,v_i\le n$）—— 表示顶点 $u_i$ 与 $v_i$ 之间存在一条边。

保证输入中的边构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $3\cdot10^5$。

For each test case, print a single line containing $n-1$ integers. The $i$-th integer represents the minimum inconvenience for $k=i$.

对于每个测试用例，输出一行包含 $n-1$ 个整数。其中第 $i$ 个整数表示当 $k=i$ 时的最小不便值。

In the first test case, possible solutions for $k=1,2,\ldots,n-1$ are as follows:

在第一个测试用例中，$k=1,2,\ldots,n-1$ 的可能解如下所示：