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 翻译