问题陈述
有一个 N- 顶点有根的二叉树,其顶点已编号 1 通过 N。根是顶点 1,以及顶点的父级 i (2 \leq i \leq N) 是顶点 p_i.每个顶点都有 恰好为零或二 孩子们。
顶点 i 有
分别是 S_i 。 S_i 是整数或字符。如果顶点是一片叶子, S_i 是一个整数;否则,要么是 + or x.
您将按任意顺序重复执行以下两种操作,直到您无法执行为止。
- 选择一个顶点,其中
其上写有
+,其子代上都写有整数。让 a 和 b 是那些整数。更换+用整数写在顶点上 a+b,然后删除孩子。 - 选择一个顶点,其中
其上写有
x,其子代上都写有整数。让 a 和 b 是那些整数。更换x用整数写在顶点上 a \times b,然后删除孩子。
完成后,将只剩下一个顶点,上面写有一个整数。求这个整数的模 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.
- S_i 是:
- 之间的整数 1 和 10^8,包含在内,如果顶点 i 是一片叶子;
- 要么
+orx如果顶点 i 不是叶子。
输入
输入由标准输入按以下格式给出:
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。 更换
x写在顶点上 2 与 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.