/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
頂点に 1 から N までの番号がついた N 頂点の根付き二分木があります。根は頂点 1 で、頂点 i (2 \leq i \leq N) の親は頂点 p_i です。すべての頂点は 子を持たないか、ちょうど 2 個の子を持つか のいずれかです。
また、頂点 i には S_i が書きこまれています。S_i は整数または文字で、二分木の葉の頂点には整数が、葉でない頂点には + または x が書かれています。
あなたは次の 2 種類の操作を自由な順番で操作を行えなくなるまで繰り返します。
- 自身に
+が書かれていて、両方の子の頂点に整数が書かれている頂点を選ぶ。子に書かれた整数をそれぞれ a, b として、頂点に書かれている+を整数 a+b に書き換える。そして、子の頂点を取り除く。 - 自身に
xが書かれていて、両方の子の頂点に整数が書かれている頂点を選ぶ。子に書かれた整数をそれぞれ a, b として、頂点に書かれているxを整数 a \times b に書き換える。そして、子の頂点を取り除く。
操作を終了した時点で、整数が書かれた頂点がちょうど 1 個残ります。その頂点に書かれた整数を 998244353 で割った余りを求めてください。(どのような順番で操作しても残った頂点に書かれている整数は同じになることが証明できます。)
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq p_i \leq i - 1 (2 \leq i \leq N)
- 全ての頂点は p_2, p_3, \dots, p_N にちょうど 0 回または 2 回現れる
- S_i は次の 2 種類のいずれか
- 頂点 i が葉の頂点のとき、S_i は 1 以上 10^8 以下の整数
- 頂点 i が葉でない頂点のとき、S_i は
+またはx
入力
入力は以下の形式で標準入力から与えられる。
N p_2 p_3 \dots p_N S_1 S_2 \dots S_N
出力
答えを出力せよ。
入力例 1
5 1 1 2 2 + x 3 2 5
出力例 1
13
以下の手順により、13 が書かれた頂点が残るので答えは 13 です。
- 頂点 2 を選ぶ。頂点 2 に書かれている
xを 2 \times 5 = 10 に書き換えて、頂点 4 と頂点 5 を削除する。 - 頂点 1 を選ぶ。頂点 1 に書かれている
+を 10 + 3 = 13 に書き換えて、頂点 2 と頂点 3 を削除する。
入力例 2
7 1 2 1 4 4 2 x + 31415 + 92653 58979 32384
出力例 2
689770791
998244353 で割った余りを求めることに注意してください。
Problem Statement
There is a N-vertex rooted binary tree whose vertices are numbered 1 through N. The root is vertex 1, and the parent of vertex i (2 \leq i \leq N) is vertex p_i. Every vertex has exactly zero or two children.
Vertex i has S_i written on it. S_i is either an integer or a character. If the vertex is a leaf, S_i is an integer; otherwise, it is either + or x.
You will repeatedly perform the following two kinds of operations in any order, until you are unable to do so.
- Choose a vertex, with
+written on it, whose children both have integers written on them. Let a and b be those integers. Replace the+written on the vertex with the integer a+b, and remove the children. - Choose a vertex, with
xwritten on it, whose children both have integers written on them. Let a and b be those integers. Replace thexwritten on the vertex with the integer a \times b, and remove the children.
Once you are done, there will be only one remaining vertex with an integer written on it. Find this integer, modulo 998244353. (One can prove that the integer written on the final vertex is unique regardless of the order of the operations.)
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq p_i \leq i - 1 (2 \leq i \leq N)
- Every vertex occurs exactly zero times or twice in p_2, p_3, \dots, p_N.
- S_i is:
- an integer between 1 and 10^8, inclusive, if vertex i is a leaf;
- either
+orxif vertex i is not a leaf.
Input
The input is given from Standard Input in the following format:
N p_2 p_3 \dots p_N S_1 S_2 \dots S_N
Output
Print the answer.
Sample Input 1
5 1 1 2 2 + x 3 2 5
Sample Output 1
13
By the following steps, there will be left a vertex with 13 written on it, so the answer is 13.
- Choose vertex 2. Replace the
xwritten on vertex 2 with 2 \times 5 = 10, and remove vertices 4 and 5. - Choose vertex 1. Replace the
+written on vertex 1 with 10 + 3 = 13, and remove vertices 2 and 3.
Sample Input 2
7 1 2 1 4 4 2 x + 31415 + 92653 58979 32384
Sample Output 2
689770791
Make sure to find the answer modulo 998244353.