分数: 650 点
问题陈述
你得到了一棵有根的树 N 顶点编号 1 to 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 不是叶子, \displaystyle f(n) = A_n + \prod_{c \in C(n)} f(c),其中 C(n) 是以下子组的集合 n.
- 有根树的哈希值为 f(1) \bmod{998244353}.
流程 Q 按给出的顺序进行查询。
每个查询都提供 v 和 x,所以更新 A_v to x ,然后计算有根树的哈希值。
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \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第一个查询。
示例输入 1
3 2 1 1 3 5 1 3 4 2 1
示例输出 1
23 7
最初, A = (3, 5, 1).
第一个查询处理如下:
- 更新 A_3 to 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 to 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 是有根树的哈希值。
示例输入 2
5 4 1 1 2 2 2 5 4 4 1 3 3 5 0 4 5 5 2
示例输出 2
29 17 17 47
示例输入 3
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
示例输出 3
876873846 952166813 626349486 341294449 466546009 331098453 469507939 414882732 86695436 199797684