AT_abc351_g [ABC351G] Hash on Tree

有一棵有 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$。 顶点 $1$ 是根，顶点 $i$（$2 \leq i \leq N$）的父节点是顶点 $p_i$，且 $p_i < i$。 另外，给定一个数列 $A = (A_1, A_2, \dots, A_N)$。 有根树的**哈希值**定义如下： - 对于 $f(n)$（$1 \leq n \leq N$），按照 $n = N, N-1, \dots, 2, 1$ 的顺序进行如下计算： - 如果顶点 $n$ 是叶子节点，则 $f(n) = A_n$。 - 如果顶点 $n$ 不是叶子节点，设 $C(n)$ 为 $n$ 的所有子节点的集合，则 $f(n) = A_n + \prod_{c \in C(n)} f(c)$。 - 有根树的哈希值为 $f(1) \bmod{998244353}$。 给定 $Q$ 个查询，请按顺序处理每个查询。 每个查询给定 $v, x$，将 $A_v$ 的值更新为 $x$，然后输出当前有根树的哈希值。

输入按以下格式从标准输入给出，其中 $\mathrm{query}_i$ 表示第 $i$ 个查询。 > $N$ $Q$ > $p_2$ $p_3$ $\dots$ $p_N$ > $A_1$ $A_2$ $\dots$ $A_N$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 每个查询的格式如下： > $v$ $x$

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个查询的答案。

### 限制条件 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq Q \leq 2 \times 10^5$ - $1 \leq p_i < i$ - $0 \leq A_i < 998244353$ - $1 \leq v \leq N$ - $0 \leq x < 998244353$ - 输入的所有值均为整数 ### 样例解释 1 初始时，$A = (3, 5, 1)$。第 1 个查询按如下方式处理： - 将 $A_3$ 更新为 $4$，此时 $A = (3, 5, 4)$。 - 有根树的哈希值按如下步骤计算为 $23$，输出 $23$。 - 顶点 $3$ 没有子节点，所以 $f(3) = 4$。 - 顶点 $2$ 没有子节点，所以 $f(2) = 5$。 - 顶点 $1$ 有子节点 $2, 3$，所以 $f(1) = 3 + 5 \times 4 = 23$。 - $f(1) \bmod{998244353} = 23$，作为有根树的哈希值。 第 2 个查询按如下方式处理： - 将 $A_2$ 更新为 $1$，此时 $A = (3, 1, 4)$。 - 有根树的哈希值按如下步骤计算为 $7$，输出 $7$。 - 顶点 $3$ 没有子节点，所以 $f(3) = 4$。 - 顶点 $2$ 没有子节点，所以 $f(2) = 1$。 - 顶点 $1$ 有子节点 $2, 3$，所以 $f(1) = 3 + 1 \times 4 = 7$。 - $f(1) \bmod{998244353} = 7$，作为有根树的哈希值。 由 ChatGPT 4.1 翻译