← 返回题目列表

Codeforces · 1976/F

F. 拆除桥梁

中文机器翻译题面 查看原题

给你一棵有根树,由 $$$n$$$ 个顶点组成,编号从 $$$1$$$ 到 $$$n$$$。顶点 $$$1$$$ 是根。此外,根只有一个子节点。

系统会要求您将 $$$k$$$ 边精确添加到树中(可能是多条边和/或树中已存在的边)。

回想一下,桥是这样一种边,当您删除它后,图中连接的组件的数量会增加。因此,最初,树的所有边缘都是桥。

添加$$$k$$$边后,树的一些原始边仍然是桥,有些不再是。你要满足两个条件:

- 对于每个桥,该桥下顶点的子树中的所有树边也应该是桥;
- 桥的数量尽可能少。

求解从 $$$1$$$ 到 $$$n - 1$$$ 的所有 $$$k$$$ 值的任务,并输出最小数量的桥。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 树的顶点数。

接下来的 $$$n - 1$$$ 行包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$) - 树边的描述。保证给定的边形成有效的树。

对输入的附加约束:根(顶点 $$$1$$$)只有一个子节点。

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

输出

对于每个测试用例,打印 $$$n - 1$$$ 整数。对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个 $$$k$$$,打印将 $$$k$$$ 边添加到树后可以留下的最小桥数。

示例

输入 #1

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

输出 #1

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