← 返回题目列表

Codeforces · 1554/E

E. 你

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

给你一棵有 $$$n$$$ 个节点的树。提醒一下,树是一个没有循环的连通无向图。

设 $$$a_1, a_2, \ldots, a_n$$$ 为整数序列。准确执行以下操作 $$$n$$$ 次:

- 选择一个未擦除的节点$$$u$$$。分配 $$$a_u :=$$$ 与 $$$u$$$ 相邻的未擦除节点数。然后,删除节点 $$$u$$$ 以及以其为端点的所有边。

对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$k$$$,找到满足以下条件的不同序列 $$$a_1, a_2, \ldots, a_n$$$ 的模 $$$998\,244\,353$$$ 的数字:

- 通过按某种顺序执行上述操作 $$$n$$$ 次,可以获得 $$$a$$$。
- $$$\operatorname{gcd}(a_1, a_2, \ldots, a_n) = k$$$。这里,$$$\operatorname{gcd}$$$表示$$$a$$$中元素的最大公约数。

输入

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

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

接下来的 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$),表示顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。保证给定的边形成一棵树。

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

输出

对于每个测试用例,在一行中打印 $$$n$$$ 整数,其中对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,第 $$$k$$$ 个整数表示当 $$$\operatorname{gcd}$$$ 等于 $$$k$$$ 时的答案。

示例

输入 #1

2
3
2 1
1 3
2
1 2

输出 #1

3 1 0
2 0

注意

在第一个测试用例中,

- 如果我们按照 $$$1 \rightarrow 2 \rightarrow 3$$$ 或 $$$1 \rightarrow 3 \rightarrow 2$$$ 的顺序删除节点,那么得到的序列将是 $$$a = [2, 0, 0]$$$,其中 $$$\operatorname{gcd}$$$ 等于 $$$2$$$。
- 如果我们按照 $$$2 \rightarrow 1 \rightarrow 3$$$ 的顺序删除节点,那么得到的序列将是 $$$a = [1, 1, 0]$$$,其中 $$$\operatorname{gcd}$$$ 等于 $$$1$$$。
- 如果我们按照 $$$3 \rightarrow 1 \rightarrow 2$$$ 的顺序删除节点,那么得到的序列将是 $$$a = [1, 0, 1]$$$,其中 $$$\operatorname{gcd}$$$ 等于 $$$1$$$。
- 如果我们按照 $$$2 \rightarrow 3 \rightarrow 1$$$ 或 $$$3 \rightarrow 2 \rightarrow 1$$$ 的顺序删除节点,那么得到的序列将是 $$$a = [0, 1, 1]$$$,其中 $$$\operatorname{gcd}$$$ 等于 $$$1$$$。

注意,这里我们计算的是不同序列的数量,而不是删除节点的不同顺序的数量。