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 翻译