AT_abc459_e [ABC459E] Select from Subtrees

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 $ .

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 the number, modulo $ 998244353 $ , of possible ways to choose the candies.

### Sample Explanation 1 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 Explanation 2 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 Explanation 3 Remember to output the count modulo $ 998244353 $ . ### 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.