G - Hash on Tree Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 650 点

問題文

頂点に 1 から N の番号がついた N 頂点の根付き木があります。
頂点 1 が根で、頂点 i (2 \leq i \leq N) の親は頂点 p_i です。(p_i \lt 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 が葉でない場合、n の子からなる集合を C(n) として \displaystyle f(n) = A_n + \prod_{c \in C(n)} f(c) とする。
  • f(1) \bmod{998244353} を根付き木のハッシュ値とする。

Q 個のクエリを与えられる順に処理してください。
各クエリでは v, x が与えられるので、A_v の値を x に更新した後、根付き木のハッシュ値を求めてください。

制約

  • 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
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \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) です。
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 を根付き木のハッシュ値とする。

2 番目のクエリは次のように処理されます。

  • 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 を根付き木のハッシュ値とする。

入力例 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

Score: 650 points

Problem Statement

You are given a rooted tree with N vertices numbered 1 to N.
Vertex 1 is the root, and the parent of vertex i (2 \leq i \leq N) is vertex p_i (p_i < i).
Additionally, there is a sequence A = (A_1, A_2, \dots, A_N).

The hash value of the rooted tree is calculated as follows:

  • Define f(n) (1 \leq n \leq N) as follows in the order n = N, N-1, \dots, 2, 1.
    • If vertex n is a leaf, f(n) = A_n.
    • If vertex n is not a leaf, \displaystyle f(n) = A_n + \prod_{c \in C(n)} f(c), where C(n) is the set of children of n.
  • The hash value of the rooted tree is f(1) \bmod{998244353}.

Process Q queries in the order they are given.
Each query provides v and x, so update A_v to x and then compute the hash value of the rooted tree.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i represents the i-th query:

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

Each query is given in the following format:

v x

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

3 2
1 1
3 5 1
3 4
2 1

Sample Output 1

23
7

Initially, A = (3, 5, 1).
The first query is processed as follows:

  • Update A_3 to 4. Now A = (3, 5, 4).
  • The hash value of the rooted tree is calculated as follows to be 23, which should be printed.
    • Vertex 3 has no children. Thus, f(3) = 4.
    • Vertex 2 has no children. Thus, f(2) = 5.
    • Vertex 1 has children 2 and 3. Thus, f(1) = 3 + 5 \times 4 = 23.
    • f(1) \bmod{998244353} = 23 is the hash value of the rooted tree.

The second query is processed as follows:

  • Update A_2 to 1. Now A = (3, 1, 4).
  • The hash value of the rooted tree is calculated as follows to be 7:
    • Vertex 3 has no children. Thus, f(3) = 4.
    • Vertex 2 has no children. Thus, f(2) = 1.
    • Vertex 1 has children 2 and 3. Thus, f(1) = 3 + 1 \times 4 = 7.
    • f(1) \bmod{998244353} = 7 is the hash value of the rooted tree.

Sample Input 2

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

Sample Output 2

29
17
17
47

Sample Input 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

Sample Output 3

876873846
952166813
626349486
341294449
466546009
331098453
469507939
414882732
86695436
199797684