E - Select from Subtrees Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N 頂点の根付き木 T があり、各頂点は頂点 1, 頂点 2, \ldots, 頂点 N と番号づけられています。
頂点 1 は T の根であり、頂点 i (2\leq i\leq N) の（直接の）親は P_i です。

また、頂点 i (1\leq i\leq N) には C_i 個のアメがあります。 ここで、(C_1+C_2+\cdots+C_N) 個のアメはすべて区別されます。

高橋君は N 匹のリスに命令を出しました。 具体的には、i 匹目 (1\leq i\leq N) のリスに次の命令を出しました。

  • 頂点 i を根とした部分木から D_i 個のアメを選んで取ってくる。

異なるリスが同じアメを取ることはできません。
アメの選ばれ方としてあり得るものの個数を 998244353 で割った余りを出力してください。

ここで、最終的に選ばれたアメの集合が同じであっても、選んだリスが異なっていれば、異なる選ばれ方として数えるものとします。
また、すべてのリスが命令通りにアメを持ってくることが不可能な場合は 0 を出力してください。

制約

  • 2\leq N\leq 2\times 10^5
  • 1\leq P_i\leq N
  • 1\leq C_i\leq 10^9
  • 1\leq D_i
  • D_1+D_2+\cdots+D_N\leq 10^6
  • 入力はすべて整数
  • T は頂点 1 を根とした根付き木

入力

入力は以下の形式で標準入力から与えられる。

N
P_2 P_3 \ldots P_N
C_1 C_2 \ldots C_N
D_1 D_2 \ldots D_N

出力

アメの選ばれ方としてあり得るものの個数を 998244353 で割った余りを出力せよ。

入力例 1

5
1 1 3 3
1 2 1 2 3
1 1 3 1 1

出力例 1

144

頂点 1,2,3,4,5 にあるアメをそれぞれアメ 1, アメ 2\cdot 3, アメ 4, アメ 5\cdot 6, アメ 7\cdot 8\cdot 9 とします。

アメの選ばれ方としては例えば次のようなものが考えられます。

  • リス 1 が頂点 1 を根とした（頂点 1,2,3,4,5 からなる）木からアメ 3 を持ってくる。
  • リス 2 が頂点 2 を根とした（頂点 2 からなる）木からアメ 2 を持ってくる。
  • リス 3 が頂点 3 を根とした（頂点 3,4,5 からなる）木からアメ 4,7,9 を持ってくる。
  • リス 4 が頂点 4 を根とした（頂点 4 のみからなる）木からアメ 6 を持ってくる。
  • リス 5 が頂点 5 を根とした（頂点 5 のみからなる）木からアメ 8 を持ってくる。

なお、これは以下のような選ばれ方とは区別されます。

  • リス 1 が頂点 1 を根とした（頂点 1,2,3,4,5 からなる）木からアメ \mathbf{2} を持ってくる。
  • リス 2 が頂点 2 を根とした（頂点 2 からなる）木からアメ \mathbf{3} を持ってくる。
  • リス 3 が頂点 3 を根とした（頂点 3,4,5 からなる）木からアメ 4,7,9 を持ってくる。
  • リス 4 が頂点 4 を根とした（頂点 4 のみからなる）木からアメ 6 を持ってくる。
  • リス 5 が頂点 5 を根とした（頂点 5 のみからなる）木からアメ 8 を持ってくる。

条件をみたす選び方は全部で 144 通りあるため、144 を 998244353 で割った余りである 144 を出力します。

入力例 2

2
1
1 1
2 1

出力例 2

0

木には頂点 1 と頂点 2 あわせて 2 個しかアメがないため、両方のリスが命令通りにアメを選ぶことはできません。
よって、0 を出力します。

入力例 3

3
3 1
1000000000 1 1
1 1 1

出力例 3

1755647

998244353 で割った余りを出力することに注意してください。

Score : 450 points

Problem Statement

There is a rooted tree T with N vertices, where the vertices are numbered as vertex 1, vertex 2, \ldots, vertex N.
Vertex 1 is the root of T, and the (direct) parent of vertex i (2 \leq i \leq N) is P_i.

Additionally, vertex i (1 \leq i \leq N) has C_i candies. All (C_1 + C_2 + \cdots + C_N) candies are distinguishable from each other.

Takahashi gave instructions to N squirrels. Specifically, he gave the following instruction to the i-th squirrel (1 \leq i \leq N):

  • Choose and collect D_i candies from the subtree rooted at vertex i.

Different squirrels cannot take the same candy.
Output the number, modulo 998244353, of possible ways to choose the candies.

Here, even if the set of candies ultimately chosen is the same, if the squirrels that chose them are different, they are counted as different ways.
If it is impossible for all squirrels to bring back candies as instructed, output 0.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq N
  • 1 \leq C_i \leq 10^9
  • 1 \leq D_i
  • D_1 + D_2 + \cdots + D_N \leq 10^6
  • All input values are integers.
  • T is a rooted tree with vertex 1 as the root.

Input

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

N
P_2 P_3 \ldots P_N
C_1 C_2 \ldots C_N
D_1 D_2 \ldots D_N

Output

Output the number, modulo 998244353, of possible ways to choose the candies.

Sample Input 1

5
1 1 3 3
1 2 1 2 3
1 1 3 1 1

Sample Output 1

144

We call the candies so that we have candy 1 at vertex 1, candies 2, 3 at vertex 2, candy 4 at vertex 3, candies 5, 6 at vertex 4, and candies 7, 8, 9 at vertex 5.

One possible way to choose the candies is as follows:

  • Squirrel 1 collects candy 3 from the tree rooted at vertex 1 (consisting of vertices 1, 2, 3, 4, 5).
  • Squirrel 2 collects candy 2 from the tree rooted at vertex 2 (consisting of vertex 2).
  • Squirrel 3 collects candies 4, 7, 9 from the tree rooted at vertex 3 (consisting of vertices 3, 4, 5).
  • Squirrel 4 collects candy 6 from the tree rooted at vertex 4 (consisting of vertex 4 only).
  • Squirrel 5 collects candy 8 from the tree rooted at vertex 5 (consisting of vertex 5 only).

Note that this is counted as a different way from the following:

  • Squirrel 1 collects candy \mathbf{2} from the tree rooted at vertex 1 (consisting of vertices 1, 2, 3, 4, 5).
  • Squirrel 2 collects candy \mathbf{3} from the tree rooted at vertex 2 (consisting of vertex 2).
  • Squirrel 3 collects candies 4, 7, 9 from the tree rooted at vertex 3 (consisting of vertices 3, 4, 5).
  • Squirrel 4 collects candy 6 from the tree rooted at vertex 4 (consisting of vertex 4 only).
  • Squirrel 5 collects candy 8 from the tree rooted at vertex 5 (consisting of vertex 5 only).

There are 144 valid ways in total, so output 144 modulo 998244353, that is, 144.

Sample Input 2

2
1
1 1
2 1

Sample Output 2

0

The tree has only two candies across vertices 1 and 2, so it is impossible for both squirrels to collect candies as instructed.
Thus, output 0.

Sample Input 3

3
3 1
1000000000 1 1
1 1 1

Sample Output 3

1755647

Remember to output the count modulo 998244353.