← 返回题目列表

AtCoder · past17_f

F. 语法树

中文机器翻译题面 查看原题

问题陈述

有一个 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 是一片叶子;
    • 要么 + or x 如果顶点 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.