#P18213. Topology

Topology

Topology

给定一棵有 nn 个节点、以节点 11 为根的树。保证每个节点的编号都小于它所有子节点的编号。

这棵树的一个拓扑序是节点 1,2,…,n1,2,\ldots,n 的一个排列 p1,p2,…,pnp_1,p_2,\ldots,p_n,满足每个父节点都出现在它的子节点之前。等价地,对于任意 1≤i<j≤n1\le i<j\le n,节点 pjp_j 都不是节点 pip_i 的父节点。

对于每个 1≤i≤n1\le i\le n,求这棵树有多少个拓扑序满足 pi=ip_i=i。答案对 998244353998244353 取模。

这里的 pi=ip_i=i 指整个拓扑序的第 ii 个位置恰好放节点 ii,不是在某棵子树内的位置。

输入格式

每个输入文件只有一组测试数据。

第一行一个整数 nn,满足 2≤n≤50002\le n\le5000,表示树的节点数。

第二行 n−1n-1 个整数 f2,f3,…,fnf_2,f_3,\ldots,f_n,其中 1≤fi<i1\le f_i<i,表示节点 ii 的父节点是 fif_i。

输出格式

输出一行 nn 个由空格分隔的整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 aia_i 是满足 pi=ip_i=i 的拓扑序个数,对 998244353998244353 取模。

样例 1

输入:

4
1 1 2

输出:

3 2 1 2

这棵树的全部拓扑序是 (1,2,3,4)(1,2,3,4)、(1,3,2,4)(1,3,2,4) 和 (1,2,4,3)(1,2,4,3)。其中有 33 个满足 p1=1p_1=1,22 个满足 p2=2p_2=2,11 个满足 p3=3p_3=3,22 个满足 p4=4p_4=4。

样例 2

输入:

9
1 1 2 2 3 3 4 5

输出:

672 420 180 160 152 108 120 170 210