AT_agc066_e.[AGC066E] Sliding Puzzle On Tree

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。树的第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

对于 $K=1,2,\ldots,N$，请解决以下问题：

有 $K$ 个编号为 $1,2,\ldots,K$ 的石子，第 $i$ 个石子初始放在顶点 $i$。你可以重复进行如下操作：

• 选择一条连接顶点 $u$ 和 $v$ 的树边，且 $u$ 上有石子而 $v$ 上没有石子。将 $u$ 上的石子移动到 $v$ 上。

求所有可能的石子最终分布方案数，答案对 $998244353$ 取模。注意，如果某个编号的石子所在顶点不同，则认为是不同的分布方案。

给定 $T$ 组测试数据，请分别输出每组的答案。

输入以如下格式从标准输入读入：

$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$

每组测试数据格式如下：

$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$

请输出 $T$ 行，每行对应一组测试数据，对于每组数据，输出 $K=1,2,\ldots,N$ 的答案，使用半角空格分隔。

限制

• $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$。

样例解释 1

用编号为 $1,2,\ldots,K$ 的石子所在顶点的编号序列表示石子的分布方案时：

• $K=1$ 时，可能的分布方案为 $(1), (2), (3), (4)$，共 $4$ 种。
• $K=2$ 时，可能的分布方案为 $(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)$，共 $12$ 种。
• $K=3$ 时，可能的分布方案为 $(1,2,3), (4,1,3), (4,2,1), (4,2,3)$，共 $4$ 种。
• $K=4$ 时，可能的分布方案为 $(1,2,3,4)$，共 $1$ 种。

对于 $K=3$ 的情况，可以参考下图：

样例解释 2

每组测试数据对应的树结构如下图所示：

由 ChatGPT 4.1 翻译