#P18288. Ying’s Cup

Ying’s Cup

Ying’s Cup

给定一棵有 nn 个顶点的无向树 T=(V,E)T=(V,E)。对于每个 k=1,2,…,nk=1,2,\ldots,n,求有多少个 1,2,…,n1,2,\ldots,n 的排列 a1,a2,…,ana_1,a_2,\ldots,a_n,使树上恰好有 kk 个顶点是局部极小值。答案对 998 244 353998\,244\,353 取模。

顶点 uu 是局部极小值,当且仅当对每条与它相连的边 (u,v)∈E(u,v)\in E,均有 au<ava_u<a_v。也就是说,它的数值严格小于所有邻居的数值。

输入格式

第一行包含一个整数 nn,满足 1≤n≤5001\le n\le500。

接下来 n−1n-1 行,每行包含两个整数 xi,yix_i,y_i,表示一条树边,满足 1≤xi,yi≤n1\le x_i,y_i\le n。

输出格式

输出 nn 行,依次给出 k=1,2,…,nk=1,2,\ldots,n 时的答案,均为模 998 244 353998\,244\,353 意义下的非负整数。

样例

5
1 2
1 3
2 4
2 5
28
54
38
0
0