103516: [Atcoder]ABC351 G - Hash on Tree
Description
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
Input
Output
问题描述
你被给定一个根节点为1的有N个顶点的树。
顶点从1到N编号，顶点i（2 ≤ i ≤ N）的父节点是顶点p_i（p_i < i）。
此外，还有一个序列A = (A_1, A_2, ..., A_N)。
树的“哈希值”计算如下：
- 按照顺序n = N, N-1, ..., 2, 1定义f(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，然后计算树的哈希值。
限制条件
- 2 ≤ N ≤ 2 × 10^5
- 1 ≤ Q ≤ 2 × 10^5
- 1 ≤ p_i < i
- 0 ≤ A_i < 998244353
- 1 ≤ v ≤ N
- 0 ≤ 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更新为4。现在A = (3, 5, 4)。
- 计算树的哈希值为23，应打印出来：
- 顶点3没有子节点。因此，f(3) = 4。
- 顶点2没有子节点。因此，f(2) = 5。
- 顶点1有子节点2和3。因此，f(1) = 3 + 5 × 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 × 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