← 返回题目列表

Codeforces · 1527/D

D. MEX 树

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

给你一棵有 $$$n$$$ 个节点的树,从 $$$0$$$ 到 $$$n-1$$$ 进行编号。对于 $$$0$$$ 和 $$$n$$$(含)之间的每个 $$$k$$$,您必须计算无序对 $$$(u,v)$$$、$$$u \neq v$$$ 的数量,使得从 $$$u$$$ 到 $$$v$$$(包括端点)的最短路径中所有节点标签的 MEX 为 $$$k$$$。

整数序列的 MEX 是不属于该序列的最小非负整数。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$)。

每个测试用例的接下来的 $$$n-1$$$ 行描述了必须构建的树。这些行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$0 \le u,v \le n-1$$$) 表示 $$$u$$$ 和 $$$v$$$ ($$$u \neq v$$$) 之间的边。

保证给定的边形成一棵树。

还保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,打印 $$$n+1$$$ 整数:树中的路径数,使得该路径中所有节点标签的 MEX 为 $$$k$$$,对于从 $$$0$$$ 到 $$$n$$$ 的每个 $$$k$$$。

示例

输入 #1

2
4
0 1
0 2
2 3
2
1 0

输出 #1

1 2 1 1 1 
0 0 1

注意

1. 在 $$$1$$$ 示例中,对于 $$$k = 0$$$,存在从 $$$2$$$ 到 $$$3$$$ 的 $$$1$$$ 路径,即 $$$MEX([2, 3]) = 0$$$。 对于 $$$k = 1$$$,存在从 $$$0$$$ 到 $$$2$$$ 的 $$$2$$$ 路径,当 $$$MEX([0, 2]) = 1$$$ 时,以及从 $$$0$$$ 到 $$$3$$$ 路径,当 $$$MEX([0, 2, 3]) = 1$$$ 时。 对于 $$$k = 2$$$,存在从 $$$0$$$ 到 $$$1$$$ 的 $$$1$$$ 路径,即 $$$MEX([0, 1]) = 2$$$。 对于 $$$k = 3$$$,存在从 $$$1$$$ 到 $$$2$$$ 的 $$$1$$$ 路径,如 $$$MEX([1, 0, 2]) = 3$$$ 对于 $$$k = 4$$$,存在从 $$$1$$$ 到 $$$3$$$ 的 $$$1$$$ 路径,如 $$$MEX([1, 0, 2, 3]) = 4$$$。
2. 在$$$2$$$示例中,对于$$$k = 0$$$,不存在这样的路径。 对于 $$$k = 1$$$,不存在这样的路径。 对于 $$$k = 2$$$,存在从 $$$0$$$ 到 $$$1$$$ 的 $$$1$$$ 路径,即 $$$MEX([0, 1]) = 2$$$。