← 返回题目列表

Codeforces · 2089/E

E. 黑猫崩溃

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

黑猫的世界正在崩溃。

在这个世界中,它可以表示为一棵有根树,根位于节点 $$$1$$$,Liki 和 Sasami 需要揭开世界的真相。

每天,他们都可以探索尚未崩溃的节点$$$u$$$。经过这次探索,黑猫导致 $$$u$$$ 及其子树中的所有节点崩溃。另外,在第$$$i$$$天结束时,如果存在,则$$$n-i+1$$$节点也会崩溃。

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,确定 Liki 和 Sasami 精确探索 $$$i$$$ 天的探索方案数量(即,他们精确执行 $$$i$$$ 操作),最后一次探索位于节点 $$$1$$$。结果应以 $$$998\,244\,353$$$ 为模进行计算。

注意: 保证节点 $$$1$$$ 到 $$$n$$$ 可以形成树的“DFS”顺序,这意味着存在深度优先搜索遍历,其中第 $$$i$$$ 访问的节点是 $$$i$$$。

输入

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

每个测试用例的第一行恰好包含一个数字 $$$n$$$ ($$$3 \le n \le 80$$$)。

以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$u_i$$$ 和 $$$v_i$$$,表示由边连接的两个顶点 ($$$1 \le u_i, v_i \le n$$$)。保证给定的边形成一棵树。还保证了顶点能够形成“DFS”遍历顺序。

保证所有测试用例的$$$n$$$总和不超过$$$80$$$

输出

对于每个测试用例,打印 $$$n$$$ 整数,其中第 $$$i$$$ 整数表示恰好 $$$i$$$ 天的探索方案数量,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

2
4
1 2
2 3
2 4
7
4 2
6 1
5 1
7 6
2 3
1 2

输出
复制

1 3 3 1
1 6 23 48 43 17 1

注意

对于第一个测试用例,以下操作序列是合法的:

$$$\{1\},\{2,1\},\{3,1\},\{4,1\},\{3,2,1\},\{4,2,1\},\{4,3,1\},\{4,3,2,1\}$$$.