树上的哈希

题目描述

给定一棵编号为 $1$ 到 $N$ 的 $N$ 个顶点的有根树。

顶点 $1$ 是根,顶点 $i$ $(2 \leq i \leq N)$ 的父节点是顶点 $p_i$ $(p_i \lt i)$。

另外,给定序列 $A = (A_1, A_2, \dots, A_N)$。

这棵有根树的哈希值按如下方式计算:

按 $n = N, N-1, \dots, 2, 1$ 的顺序定义 $f(n)$ $(1 \leq n \leq N)$。

如果顶点 $n$ 是叶子,则 $f(n) = A_n$。

如果顶点 $n$ 不是叶子,则 $\displaystyle f(n) = A_n + \prod_{c \in C(n)} f(c)$,其中 $C(n)$ 是 $n$ 的子节点集合。

这棵有根树的哈希值是 $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$ 个查询的答案。

样例

3 2
1 1
3 5 1
3 4
2 1

23
7

初始时,$A = (3, 5, 1)$。

第一个查询按如下方式处理:

将 $A_3$ 更新为 $4$。此时 $A = (3, 5, 4)$。

这棵有根树的哈希值计算如下,得到 $23$,应输出该值。

顶点 $3$ 没有子节点。因此,$f(3) = 4$。

顶点 $2$ 没有子节点。因此,$f(2) = 5$。

顶点 $1$ 有子节点 $2$ 和 $3$。因此,$f(1) = 3 + 5 \times 4 = 23$。

$f(1) \bmod{998244353} = 23$ 就是这棵有根树的哈希值。

第二个查询按如下方式处理:

将 $A_2$ 更新为 $1$。此时 $A = (3, 1, 4)$。

这棵有根树的哈希值计算如下,得到 $7$:

顶点 $3$ 没有子节点。因此,$f(3) = 4$。

顶点 $2$ 没有子节点。因此,$f(2) = 1$。

顶点 $1$ 有子节点 $2$ 和 $3$。因此,$f(1) = 3 + 1 \times 4 = 7$。

$f(1) \bmod{998244353} = 7$ 就是这棵有根树的哈希值。

5 4
1 1 2 2
2 5 4 4 1
3 3
5 0
4 5
5 2

29
17
17
47

10 10
1 2 1 2 5 6 3 5 1
766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044
1 21524934
9 529970099
6 757265587
8 219853537
5 687675301
5 844033519
8 780395611
2 285523485
6 13801766
3 487663184

876873846
952166813
626349486
341294449
466546009
331098453
469507939
414882732
86695436
199797684

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq p_i \lt i$
• $0 \leq A_i \lt 998244353$
• $1 \leq v \leq N$
• $0 \leq x \lt 998244353$
• 输入中的所有值均为整数。