[ABC351] G - Hash on Tree

G - Hash on Tree

Time Limit: 4 sec / Memory Limit: 1024 MB

分数: 650 分

题面

给定一个有 个顶点的根树，顶点编号为 到 。
顶点 是根，顶点 的父节点是顶点 。
此外，有一个序列 。

根树的 哈希值 计算如下：

• 顺序定义 如下:
  • 如果顶点 是叶子节点，则 。
  • 如果顶点 不是叶子节点，则 ，其中 是顶点 的子节点集合。
• 根树的哈希值为 。

按顺序处理 个查询。
每个查询提供 和 ，更新 为 ，然后计算根树的哈希值。

限制条件

• 所有输入值均为整数。

---

输入

从标准输入中以以下格式给出输入，其中 表示第 个查询:

每个查询以以下格式给出:

输出

输出 行。第 行应包含第 个查询的答案。

---

输入样例 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