#C. [NOI 2023 联合省选] 人员调度(文件输入输出)

    传统题 文件IO:transfer 5000ms 512MiB

[NOI 2023 联合省选] 人员调度(文件输入输出)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

众所周知,一个公司的 nn 个部门可以组织成一个树形结构。形式化地,假设这些部门依次编号为 1,,n1, \ldots, n,那么除了 11 号部门以外,第 i[2,n]i \in [2, n] 个部门有且仅有一个上级部门 pi[1,i1]p_i \in [1, i - 1]。这样,这家公司的 nn 个部门可以视为一个以 11 为根的树。如果 iijj 子树中的点,那么称部门 ii 是部门 jj 的子部门。

该公司初始时有 kk 名优秀员工,编号依次为 1k1 \ldots k。第 ii 名优秀员工初始时在第 xix_i 个部门工作,并且其有一个能力值 vi>0v_i > 0

为了最大化公司的运作效率,公司老板 0/\/\G 决定进行一些人员调动。具体来说,可以将编号为 ii 的优秀员工调动到 xix_i 的一个子部门,或者不调度(此时该员工在 xix_i 部门)。随后,优秀员工们会在其所在的部门竞选部门领导——能力值最高者将担任这一职位,并给公司带来等同于其能力值的贡献。如果一个部门一个优秀员工也没有,那么就无法选出部门领导,从而对公司的贡献将是 00。此时,公司的业绩被定义为公司各部门的贡献之和。

公司老板 0/\/\G 自然想知道,该如何进行人员调动,使公司的业绩最大?

这当然难不倒他,然而,公司优秀员工的数量也会发生变化;具体来说,会依次发生 mm 个事件,每个事件形如:

  • 1 x v:先令 k=k+1k = k + 1,然后新增一位编号为 kk、初始部门为 xx、能力值为 vv 的优秀员工;
  • 2 id:编号为 id\mathit{id} 的优秀员工将被辞退。

公司老板 0/\/\G 希望你能在最开始和每个事件发生后,告诉他公司的业绩最大可能是多少?

注意,每次人员调动都是独立的,也就是每次计算公司的最大可能业绩时,每个优秀员工都会回到其所在的初始部门。

输入格式

输入的第一行包含一个正整数 sid\mathit{sid},表示该测试点对应的数据范围以及特殊性质,详见后表;

输入的第二行包含三个整数 n,k,mn, k, m,分别表示部门数,初始优秀员工数和事件数。

输入的第三行包含 n1n - 1 个正整数 p2,,pnp_2, \ldots, p_n,表示每个部门的上级部门。

接下来 kk 行,每行包含两个正整数 xi,vix_i, v_i,表示优秀员工的初始部门和能力值。

接下来 mm 行,每行形如 1 x v2 id 表示一次事件。

输出格式

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

样例 #1

样例输入 #1

1
3 2 1
1 1
2 1
1 3
1 2 2

样例输出 #1

4 5

提示

【数据范围】

对于所有的数据,保证:1sid151 \le \mathit{sid} \le 151n,k1051 \le n, k \le 10^50m1050 \le m \le 10^51pi<i1 \le p_i < i1xi,xn1 \le x_i, x \le n1vi,v1051 \le v_i, v \le 10^5

对于事件 2,保证:1idk1 \le \mathit{id} \le k 且编号为 id\mathit{id} 的员工在此事件发生仍在工作。

测试点编号 sid\mathit{sid} nn \le kk \le mm \le 特殊性质
1 11 66 66
2, 3 22 99
4, 5 33 1616 6666 6666
6 ~ 8 44 6666 00
9 ~ 11 55 2,3332,333
12 ~ 14 66 10510^5 B
15 ~ 18 77
19 ~ 21 88 2,3332,333 A
22 ~ 24 99 10510^5 AB
25 ~ 28 1010 A
29 ~ 31 1111 2,3332,333
32 ~ 34 1212 10510^5 C
35 ~ 38 1313 B
39 ~ 44 1414 66,66666,666
45 ~ 50 1515 10510^5

特殊性质 A:无事件 2。

特殊性质 B:pi=i1p_i = i - 1

特殊性质 C:vi=v=1v_i = v = 1

2023 NOI 省选 CQ 批量评测(云斗学院版数据)

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-4-2 23:00
结束于
2023-4-3 0:00
持续时间
1 小时
主持人
参赛人数
112