[NOI 2023 联合省选] 人员调度(文件输入输出)
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
众所周知,一个公司的 个部门可以组织成一个树形结构。形式化地,假设这些部门依次编号为 ,那么除了 号部门以外,第 个部门有且仅有一个上级部门 。这样,这家公司的 个部门可以视为一个以 为根的树。如果 是 子树中的点,那么称部门 是部门 的子部门。
该公司初始时有 名优秀员工,编号依次为 。第 名优秀员工初始时在第 个部门工作,并且其有一个能力值 。
为了最大化公司的运作效率,公司老板 0/\/\G 决定进行一些人员调动。具体来说,可以将编号为 的优秀员工调动到 的一个子部门,或者不调度(此时该员工在 部门)。随后,优秀员工们会在其所在的部门竞选部门领导——能力值最高者将担任这一职位,并给公司带来等同于其能力值的贡献。如果一个部门一个优秀员工也没有,那么就无法选出部门领导,从而对公司的贡献将是 。此时,公司的业绩被定义为公司各部门的贡献之和。
公司老板 0/\/\G 自然想知道,该如何进行人员调动,使公司的业绩最大?
这当然难不倒他,然而,公司优秀员工的数量也会发生变化;具体来说,会依次发生 个事件,每个事件形如:
1 x v
:先令 ,然后新增一位编号为 、初始部门为 、能力值为 的优秀员工;2 id
:编号为 的优秀员工将被辞退。
公司老板 0/\/\G 希望你能在最开始和每个事件发生后,告诉他公司的业绩最大可能是多少?
注意,每次人员调动都是独立的,也就是每次计算公司的最大可能业绩时,每个优秀员工都会回到其所在的初始部门。
输入格式
输入的第一行包含一个正整数 ,表示该测试点对应的数据范围以及特殊性质,详见后表;
输入的第二行包含三个整数 ,分别表示部门数,初始优秀员工数和事件数。
输入的第三行包含 个正整数 ,表示每个部门的上级部门。
接下来 行,每行包含两个正整数 ,表示优秀员工的初始部门和能力值。
接下来 行,每行形如 1 x v
或 2 id
表示一次事件。
输出格式
输出一行包含 个由单个空格隔开的非负整数,依次表示最开始和每个事件发生后,公司的业绩可能的最大值。
样例 #1
样例输入 #1
1
3 2 1
1 1
2 1
1 3
1 2 2
样例输出 #1
4 5
提示
【数据范围】
对于所有的数据,保证:;;;;;。
对于事件 2,保证: 且编号为 的员工在此事件发生仍在工作。
测试点编号 | 特殊性质 | ||||
---|---|---|---|---|---|
1 | 无 | ||||
2, 3 | |||||
4, 5 | |||||
6 ~ 8 | |||||
9 ~ 11 | |||||
12 ~ 14 | B | ||||
15 ~ 18 | 无 | ||||
19 ~ 21 | A | ||||
22 ~ 24 | AB | ||||
25 ~ 28 | A | ||||
29 ~ 31 | 无 | ||||
32 ~ 34 | C | ||||
35 ~ 38 | B | ||||
39 ~ 44 | 无 | ||||
45 ~ 50 |
特殊性质 A:无事件 2。
特殊性质 B:。
特殊性质 C:。
2023 NOI 省选 ZJ 批量评测(云斗学院版数据)
- 状态
- 已结束
- 规则
- IOI
- 题目
- 6
- 开始于
- 2023-4-2 22:00
- 结束于
- 2023-4-2 23:30
- 持续时间
- 1.5 小时
- 主持人
- 参赛人数
- 153