分数: 1500 点
问题陈述
你有一棵树 N 顶点编号 1 to N.The i树的第一条边连接顶点 u_i 和 v_i.
对于每个 K=1, 2, \ldots, N,解决以下问题:
有 K 石头编号 1, 2, \ldots, K,石头编号 i 放置在顶点上 i。 您可以重复执行以下操作:
- 选择两个顶点 u 和 v 由边连接,使得 u 上面有一块石头,并且 v 没有。把石头从 u to v.
求模数 998244353,执行操作后宝石的可能配置。当且仅当有一颗石子的位置在这两种配置之间不同时,两种配置才能被区分。
T 给出了测试用例;解决它们中的每一个。
约束
- 1\leq T\leq 10^5
- 1\leq N\leq 2\times 10^5
- 1\leq u_i, v_i\leq N
- 给定的图是一棵树。
- 总和 一个输入文件中的 N 单个输入中的所有测试用例最多 2\times 10^5.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N
u_1 v_1
\vdots
u_{N-1} v_{N-1}
输出
打印 T 行。的 i- 第行应包含以下问题的答案 K=1, 2, \ldots, N 为 i-第一个测试用例,用空格分隔。
样本输入 1
1 4 1 2 1 3 1 4
示例输出 1
4 12 4 1
让我们通过棋子编号的顶点序列来表示棋子的配置 放置了 1, 2, \ldots, K 。
- 对于 K=1,有 4 可能的配置: (1), (2), (3), (4).
- 对于 K=2,有 12 可能的配置: (1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3).
- 对于 K=3,有 4 可能的配置: (1,2,3), (4,1,3), (4,2,1), (4,2,3).
- 对于 K=4,有 1 可能的配置: (1,2,3,4).
对于 K=3,参见下图。

示例输入 2
4 1 5 1 4 5 2 3 4 2 1 7 1 7 2 7 5 6 4 1 1 6 3 6 10 1 2 2 3 3 4 4 5 5 6 2 7 3 8 4 9 5 10
示例输出 2
1 5 10 10 5 1 7 42 210 840 84 7 1 10 90 720 5040 30240 151200 604800 720 10 1
每个测试用例中给出的树如下:
