#P17714. [2026年江苏省队集训]粒子发生器

[2026年江苏省队集训]粒子发生器

题目描述

小Z获得了一个粒子发生器!

粒子发生器一次可以制造 nn 个粒子,编号为 1,2,…,n1,2,\dots,n。每个粒子会被赋予一个能级,所有粒子的能级恰好构成 11 到 nn 的一个排列——也就是说,每个整数恰好出现一次。能级的数值越小,代表粒子的能量越低,状态越稳定。

粒子之间存在着相互作用,这些相互作用构成了一棵树:如果两个粒子之间有边,则它们可以直接交换能量。小Z发现,如果一个粒子的能级严格小于它所有邻居的能级,那么这个粒子就会处于基态——它是局部区域中最稳定的存在。

现在,小Z想知道:对于每个可能的 k=1,2,…,nk = 1,2,\dots,n,有多少种不同的能级分配方案,使得恰好有 kk 个粒子处于基态?

由于答案可能非常巨大,你只需输出对 998,244,353998,244,353 取模后的结果。小Z百思不得其解,请你帮他计算一下吧!

输入格式

第一行一个整数 nn。

接下来 n−1n-1 行,每行两个整数 u,vu,v,表示粒子 uu 和粒子 vv 之间存在相互作用。

输出格式

共 nn 行,每行一个整数。第 ii 行的整数表示 k=ik=i 时的方案数模 998,244,353998,244,353 的结果。

样例1输入

3
1 2
1 3

样例1输出

4
2
0

样例1解释:

粒子1处在基态的方案有 {1,2,3},{1,3,2}\{1,2,3\},\{1,3,2\}。

粒子2处在基态的方案有 {2,1,3}\{2,1,3\}。

粒子3处在基态的方案有 {2,3,1}\{2,3,1\}。

粒子2,3处在基态的方案有 {3,1,2},{3,2,1}\{3,1,2\},\{3,2,1\}。

其余情况不会出现。

样例2输入

5
1 2
1 3
2 4
2 5

样例2输出

28
54
38
0
0

数据范围

对于所有测试数据,n≤500n\leq 500 且保证输入的图是一棵树。

子任务编号 分值 n 图形态
1 10 ≤10\leq 10 树
2 5 ≤18\leq 18
3 10 ≤500\leq 500 菊花
4 5 ≤50\leq 50 链
5 ≤100\leq 100
6 10 ≤500\leq 500
7 15 ≤50\leq 50 树
8 10 ≤100\leq 100
9 ≤200\leq 200
10 20 ≤500\leq 500