← 返回题目列表

AtCoder · abc351_g

G. 树上的哈希

中文机器翻译题面 查看原题

分数: 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