众所周知，一个公司的 n 个部门可以组织成一个树形结构。形式化地，假设这些部门依次编号为 1,…,n，那么除了 1 号部门以外，第 i∈[2,n] 个部门有且仅有一个上级部门 pi∈[1,i−1]。这样，这家公司的 n 个部门可以视为一个以 1 为根的树。如果 i 是 j 子树中的点，那么称部门 i 是部门 j 的子部门。
该公司初始时有 k 名优秀员工，编号依次为 1…k。第 i 名优秀员工初始时在第 xi 个部门工作，并且其有一个能力值 vi>0。
为了最大化公司的运作效率，公司老板 0/\/\G 决定进行一些人员调动。具体来说，可以将编号为 i 的优秀员工调动到 xi 的一个子部门，或者不调度（此时该员工在 xi 部门）。随后，优秀员工们会在其所在的部门竞选部门领导——能力值最高者将担任这一职位，并给公司带来等同于其能力值的贡献。如果一个部门一个优秀员工也没有，那么就无法选出部门领导，从而对公司的贡献将是 00。此时，公司的业绩被定义为公司各部门的贡献之和。
公司老板 0/\/\G 自然想知道，该如何进行人员调动，使公司的业绩最大？
这当然难不倒他，然而，公司优秀员工的数量也会发生变化；具体来说，会依次发生 m 个事件，每个事件形如：

• 1 x v：先令 k=k+1，然后新增一位编号为 k、初始部门为 x、能力值为 v 的优秀员工；
• 2 id：编号为 id 的优秀员工将被辞退。

公司老板 0/\/\G 希望你能在最开始和每个事件发生后，告诉他公司的业绩最大可能是多少？
注意，每次人员调动都是独立的，也就是每次计算公司的最大可能业绩时，每个优秀员工都会回到其所在的初始部门。

输入的第一行包含一个正整数 sid，表示该测试点对应的数据范围以及特殊性质，详见后表；
输入的第二行包含三个整数 n,k,m，分别表示部门数，初始优秀员工数和事件数。
输入的第三行包含 n−1 个正整数 p2,…,pn，表示每个部门的上级部门。
接下来 k 行，每行包含两个正整数 xi,vi，表示优秀员工的初始部门和能力值。
接下来 m 行，每行形如 1 x v 或 2 id 表示一次事件。

输出一行包含 m+1 个由单个空格隔开的非负整数，依次表示最开始和每个事件发生后，公司的业绩可能的最大值。

特殊性质 A：无事件 2；
特殊性质 B：pi=i−1；
特殊性质 C：vi=v=1。


样例：transfer.zip

2023 省选 第三题