Hash on Tree

题目描述

有一棵包含 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$，根为顶点 $1$。对于每个 $2\le i\le N$，顶点 $i$ 的父亲是 $p_i$，并且 $p_i<i$。

每个顶点 $i$ 有一个权值 $A_i$。按照从编号大到编号小的顺序定义 $f(i)$：

• 若顶点 $i$ 是叶子，则 $f(i)=A_i$；
• 否则，设 $C(i)$ 为顶点 $i$ 的所有儿子组成的集合，则

树的哈希值定义为 $f(1)\bmod 998244353$。

你需要依次处理 $Q$ 次修改。每次修改给出 $v,x$，把 $A_v$ 改为 $x$，并输出修改后树的哈希值。

输入格式

第一行输入两个整数 $N,Q$。

第二行输入 $N-1$ 个整数 $p_2,p_3,\ldots,p_N$。

第三行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

接下来 $Q$ 行，每行输入两个整数 $v,x$，表示把 $A_v$ 修改为 $x$。

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 次修改后的树哈希值。

样例输入 1

3 2
1 1
3 5 1
3 4
2 1

样例输出 1

23
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

数据范围

• $2\le N\le 2\times 10^5$；
• $1\le Q\le 2\times 10^5$；
• $1\le p_i<i$；
• $0\le A_i<998244353$；
• $1\le v\le N$；
• $0\le x<998244353$；
• 所有输入均为整数。

样例解释 1

第一次修改后 $A=(3,5,4)$，两个叶子的值分别为 $5,4$，所以根的值为 $3+5\times4=23$。

第二次修改后 $A=(3,1,4)$，根的值为 $3+1\times4=7$。