CF1976F.Remove Bridges

给定一棵有根树，包含 $n$ 个顶点，编号从 $1$ 到 $n$，顶点 $1$ 是根节点。此外，根节点只有一个子节点。

你需要在树上恰好添加 $k$ 条边（可以是重边，也可以是已经存在的边）。

回忆一下，桥是指这样一条边：如果移除它，图中的连通分量数会增加。因此，初始时树中的所有边都是桥。

在添加了 $k$ 条边后，树中某些原有的边仍然是桥，而有些则不再是桥。你需要满足以下两个条件：

• 对于每一条桥，该桥的下端点的子树中的所有树边也必须是桥；
• 桥的数量要尽可能少。

对于每个 $k$ 从 $1$ 到 $n-1$，求出添加 $k$ 条边后，桥的最小数量。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 3 \times 10^5$），表示树的顶点数。

接下来的 $n-1$ 行，每行包含两个整数 $v$ 和 $u$（$1 \le v, u \le n$），表示树中的一条边。保证给定的边构成一棵合法的树。

输入的额外约束：根节点（顶点 $1$）恰好有一个子节点。

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

对于每个测试用例，输出 $n-1$ 个整数。对于每个 $k$ 从 $1$ 到 $n-1$，输出添加 $k$ 条边后，桥的最小数量。

由 ChatGPT 4.1 翻译