← 返回题目列表

AtCoder · agc066_e

E. 在树上滑动拼图

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

分数: 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

每个测试用例中给出的树如下: