AT_past17_f.構文木

有一棵 $N$ 个结点的二叉树，编号为 $1$ 到 $N$。根结点为 $1$ 号结点，对于第 $i$ 个结点（$2 \leq i \leq N$），其父亲为 $p_i$。每个结点的子结点数要么为 $0$，要么为 $2$。

第 $i$ 个结点上写有 $S_i$。$S_i$ 可以是一个整数，也可以是一个字符。如果该结点是叶子结点，则 $S_i$ 是一个整数；否则，$S_i$ 为“+”或“x”。

你会不断重复下面两种操作中的任意一个，知道无法再进行为止：

• 选择一个写有“+”的结点，其两个子结点上都写有整数。设这两个整数为 $a$ 和 $b$。将该结点上的“+”替换为 $a+b$，并删除这两个子结点。
• 选择一个写有“x”的结点，其两个子结点上都写有整数。设这两个整数为 $a$ 和 $b$。将该结点上的“x”替换为 $a \times b$，并删除这两个子结点。

最终，树上只会剩下一个结点且上面写有一个整数。请输出这个整数对 $998244353$ 取模的结果。（可以证明，无论操作顺序如何，最终结果唯一。）

输入按下列格式给出：

$N$ $p_2$ $p_3$ $\dots$ $p_N$ $S_1$ $S_2$ $\dots$ $S_N$

输出答案。

样例解释 1

通过以下步骤，最终会剩下一个结点，上面写着 $13$，因此答案为 $13$。

• 选择结点 $2$，将其“x”替换为 $2 \times 5 = 10$，并删除结点 $4$ 和 $5$。
• 选择结点 $1$，将其“+”替换为 $10 + 3 = 13$，并删除结点 $2$ 和 $3$。

样例解释 2

请注意最后输出时需要对 $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$ 满足：
  • 如果第 $i$ 个结点是叶子结点，$S_i$ 是 $1$ 到 $10^8$ 之间的一个整数；
  • 如果第 $i$ 个结点不是叶子结点，$S_i$ 为“+”或“x”。

由 ChatGPT 5 翻译