E - Child to Parent Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1400 点

問題文

頂点に 1 から N の番号がついた N 頂点の根付き木があります．頂点 1 が根であり，頂点 i (2\leq i\leq N) の親は P_i です．

非負整数 r および非負整数列 A = (A_1, \ldots, A_N) が与えられます．あなたはこの数列に対して，次の操作を何度でも行うことができます（0 回でもよい）：

  • i\geq 2 かつ A_i \geq 1 となる i をひとつ選ぶ．A_i を A_i - 1 に，A_{P_i} を A_{P_i}+r に置き換える．

最終的な非負整数列 A としてありうるものの個数を 998244353 で割った余りを求めてください．

制約

  • 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

出力

最終的な非負整数列 A としてありうるものの個数を 998244353 で割った余りを出力してください．

入力例 1

3
1 1
2
1 1 1

出力例 1

4

最終的な A としてありうるのは次の 4 個です：(1,1,1), (3,0,1), (3,1,0), (5,0,0)．

入力例 2

3
1 2
1
1 1 1

出力例 2

5

最終的な A としてありうるのは次の 5 個です：(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 としてありうるのは次の 6 個です：(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

Score : 1400 points

Problem Statement

There is a rooted tree with N vertices numbered 1 to N. Vertex 1 is the root, and the parent of vertex i (2\leq i\leq N) is P_i.

You are given a non-negative integer r and a sequence of non-negative integers A = (A_1, \ldots, A_N). You can perform the following operation on the sequence any number of times, possibly zero.

  • Choose an i such that i\geq 2 and A_i \geq 1. Replace A_i with A_i - 1 and A_{P_i} with A_{P_i}+r.

Find the number, modulo 998244353, of possible final states of the sequence A.

Constraints

  • 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

Input

The input is given from Standard Input in the following format:

N
P_2 \ldots P_N
r
A_1 \ldots A_N

Output

Print the number, modulo 998244353, of possible final states of the sequence A.

Sample Input 1

3
1 1
2
1 1 1

Sample Output 1

4

The four possible final states of A are (1,1,1), (3,0,1), (3,1,0), and (5,0,0).

Sample Input 2

3
1 2
1
1 1 1

Sample Output 2

5

The five possible final states of A are (1,1,1), (1,2,0), (2,0,1), (2,1,0), and (3,0,0).

Sample Input 3

3
1 2
2
1 1 1

Sample Output 3

6

The six possible final states of A are (1,1,1), (1,3,0), (3,0,1), (3,2,0), (5,1,0), and (7,0,0).

Sample Input 4

5
1 1 3 3
2
0 1 0 1 2

Sample Output 4

48

Sample Input 5

5
1 1 3 3
123456789
1 2 3 4 5

Sample Output 5

87782255