← 返回题目列表

AtCoder · agc063_e

E. 孩子对父母

中文机器翻译题面 查看原题

分数: 1400 点

问题陈述

有一棵有根的树 N 顶点编号 1 to N。顶点 1 是根,也是顶点的父级 i (2\leq i\leq N) 是 P_i.

给你一个非负整数 r 和非负整数序列 A = (A_1, \ldots, A_N)。您可以对序列执行以下操作任意次数,可能为零。

  • 选择一个 i 这样 i\geq 2 和 A_i \geq 1。更换 A_i 与 A_i - 1 和 A_{P_i} 与 A_{P_i}+r.

求模数 998244353,序列可能的最终状态 A.

约束

  • 2\leq N\leq 300
  • 1\leq P_i \leq i - 1 (2\leq i\leq N)
  • 0\leq r \leq 10^9
  • 0\leq A_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N
P_2 \ldots P_N
r
A_1 \ldots A_N

输出

打印数字,模数 998244353,序列可能的最终状态 A.


示例输入 1

3
1 1
2
1 1 1

示例输出 1

4

四种可能的最终状态 A 是 (1,1,1), (3,0,1), (3,1,0),和 (5,0,0).


示例输入 2

3
1 2
1
1 1 1

示例输出 2

5

的五种可能的最终状态 A 是 (1,1,1), (1,2,0), (2,0,1), (2,1,0),和 (3,0,0).


示例输入 3

3
1 2
2
1 1 1

示例输出 3

6

六种可能的最终状态 A 是 (1,1,1), (1,3,0), (3,0,1), (3,2,0), (5,1,0),和 (7,0,0).


示例输入 4

5
1 1 3 3
2
0 1 0 1 2

示例输出 4

48

示例输入 5

5
1 1 3 3
123456789
1 2 3 4 5

示例输出 5

87782255