#P18471. Random Tree Parking

Random Tree Parking

Random Tree Parking

停车函数是一种组合对象,最初由 Konheim 和 Weiss 在研究哈希表的线性探测冲突处理方法时引入。作为狂热的数学爱好者,Bobo 想研究树上的停车函数。

考虑一个形状为树 TT 的停车场。树有 nn 个顶点,编号为 [n]={1,2,…,n}[n]=\{1,2,\ldots,n\},以顶点 11 为根,每条边都指向根的方向。共有 nn 名司机,第 ii 名司机有一个偏好的停车位 si∈[n]s_i\in[n]。

司机按照 1,2,…,n1,2,\ldots,n 的顺序依次到达。每名司机先尝试停在自己偏好的顶点:如果该顶点为空,就停在那里;否则沿着指向根的边行驶,停在途中遇到的第一个空顶点。如果沿这条路径找不到空顶点,就离开停车场,停车失败。

如果序列 s=(s1,…,sn)∈[n]ns=(s_1,\ldots,s_n)\in[n]^n 能让所有司机都成功停车,就称它为树 TT 的一个停车函数。

例如,下图的树只有两个顶点。序列 (1,1)(1,1) 不是停车函数,序列 (1,2)(1,2)、(2,1)(2,1)、(2,2)(2,2) 是它的三个停车函数。

原题停车过程:先到的司机为橙色,后到的为绿色

原题另外两个成功停车过程

现在给定一棵有 nn 个顶点的树 TT,求它的停车函数数量。Bobo 也热衷于随机性,因此树按以下方式随机生成:对于每个 i=2,…,ni=2,\ldots,n,独立地从 {1,…,i−1}\{1,\ldots,i-1\} 中等概率选择顶点 pip_i,并让顶点 ii 指向 pip_i。

答案可能很大,请输出它对质数 998244353998244353 取模的结果。这里求的是输入这棵树的停车函数数量。

输入格式

第一行一个整数 nn(2≤n≤1052\le n\le 10^5),表示树的顶点数。

第二行有 n−1n-1 个整数 p2,p3,…,pnp_2,p_3,\ldots,p_n(1≤pi≤i−11\le p_i\le i-1),其中 pip_i 表示顶点 ii 指向的唯一顶点。可以假设各个 pip_i 都是独立地从 {1,…,i−1}\{1,\ldots,i-1\} 中等概率选出的。

原题保证本题测试集数量不超过 2020。每个输入文件是一棵树,没有多组数据的组数 TT。

输出格式

输出一个整数,表示输入树的停车函数数量对 998244353998244353 取模的结果。

样例 1

输入:

3
1 1

输出:

12

样例 2

输入:

3
1 2

输出:

16

样例 3

输入:

4
1 2 3

输出:

125

样例 4

输入:

8
1 2 3 1 3 4 3

输出:

1198736

样例 5

输入:

15
1 2 2 2 2 3 3 2 7 7 3 10 3 13

输出:

938578089