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$ 个查询的答案。

输入输出样例 #1

输入 #1

3 2
1 1
3 5 1
3 4
2 1

输出 #1

23
7

输入输出样例 #2

输入 #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

输入 #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

说明/提示

限制条件

• $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 翻译