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)$。 该有根树的 哈希值 按如下方式计算：

按顺序 $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

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 < i 0 \leq A_i < 998244353 $1 \leq v \leq N$ 0 \leq x < 998244353 所有输入值均为整数。初始时，$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$ 是该有根树的哈希值。

标签: AtCoder|abc351G

来源

AtCoder|abc351G