311378: CF1976F. Remove Bridges

F. Remove Bridgestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a rooted tree, consisting of $n$ vertices, numbered from $1$ to $n$. Vertex $1$ is the root. Additionally, the root only has one child.

You are asked to add exactly $k$ edges to the tree (possibly, multiple edges and/or edges already existing in the tree).

Recall that a bridge is such an edge that, after you remove it, the number of connected components in the graph increases. So, initially, all edges of the tree are bridges.

After $k$ edges are added, some original edges of the tree are still bridges and some are not anymore. You want to satisfy two conditions:

• for every bridge, all tree edges in the subtree of the lower vertex of that bridge should also be bridges;
• the number of bridges is as small as possible.

Solve the task for all values of $k$ from $1$ to $n - 1$ and output the smallest number of bridges.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the number of vertices of the tree.

Each of the next $n - 1$ lines contain two integers $v$ and $u$ ($1 \le v, u \le n$) — the description of the edges of the tree. It's guaranteed that the given edges form a valid tree.

Additional constraint on the input: the root (vertex $1$) has exactly one child.

The sum of $n$ over all testcases doesn't exceed $3 \cdot 10^5$.

Output

For each testcase, print $n - 1$ integers. For each $k$ from $1$ to $n - 1$ print the smallest number of bridges that can be left after you add $k$ edges to the tree.

ExampleInput

4
2
1 2
12
4 10
5 12
12 11
3 6
9 6
1 6
12 7
11 6
2 11
10 9
10 8
8
1 2
2 3
2 4
3 5
3 6
4 7
4 8
5
1 2
2 3
3 4
4 5

Output

0 
7 3 1 0 0 0 0 0 0 0 0 
4 1 0 0 0 0 0 
0 0 0 0 

题目大意：
给定一棵有根树，包含n个顶点，编号从1到n。顶点1是根，并且根只有一个孩子。要求向树中添加恰好k条边（可能是多条边，或者树中已经存在的边）。在添加k条边之后，需要满足两个条件：1）对于每座桥，桥较低顶点子树中的所有树边也都必须是桥；2）桥的数量尽可能少。对于k从1到n-1的所有值，输出剩余桥的最小数量。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
每个测试用例的第一行包含一个整数n（2≤n≤3×10^5），表示树的顶点数量。
接下来n-1行，每行包含两个整数v和u（1≤v,u≤n），表示树边的描述。保证给出的边构成一棵有效的树。
附加条件：根（顶点1）恰好有一个孩子。
所有测试用例的n之和不超过3×10^5。

输出数据格式：
对于每个测试用例，输出n-1个整数。对于每个k从1到n-1，输出在添加k条边到树后剩余的最小桥数量。

示例：
输入：
4
2
1 2
12
4 10
5 12
12 11
3 6
9 6
1 6
12 7
11 6
2 11
10 9
10 8
8
1 2
2 3
2 4
3 5
3 6
4 7
4 8
5
1 2
2 3
3 4
4 5
输出：
0
7 3 1 0 0 0 0 0 0 0 0
4 1 0 0 0 0 0
0 0 0 0题目大意： 给定一棵有根树，包含n个顶点，编号从1到n。顶点1是根，并且根只有一个孩子。要求向树中添加恰好k条边（可能是多条边，或者树中已经存在的边）。在添加k条边之后，需要满足两个条件：1）对于每座桥，桥较低顶点子树中的所有树边也都必须是桥；2）桥的数量尽可能少。对于k从1到n-1的所有值，输出剩余桥的最小数量。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 每个测试用例的第一行包含一个整数n（2≤n≤3×10^5），表示树的顶点数量。 接下来n-1行，每行包含两个整数v和u（1≤v,u≤n），表示树边的描述。保证给出的边构成一棵有效的树。 附加条件：根（顶点1）恰好有一个孩子。 所有测试用例的n之和不超过3×10^5。 输出数据格式： 对于每个测试用例，输出n-1个整数。对于每个k从1到n-1，输出在添加k条边到树后剩余的最小桥数量。 示例： 输入： 4 2 1 2 12 4 10 5 12 12 11 3 6 9 6 1 6 12 7 11 6 2 11 10 9 10 8 8 1 2 2 3 2 4 3 5 3 6 4 7 4 8 5 1 2 2 3 3 4 4 5 输出： 0 7 3 1 0 0 0 0 0 0 0 0 4 1 0 0 0 0 0 0 0 0 0