{"problem":{"name":"[省选联考 2023] 人员调度","description":{"content":"众所周知，一个公司的 $n$ 个部门可以组织成一个树形结构。形式化地，假设这些部门依次编号为 $1, \\ldots, n$，那么除了 $1$ 号部门以外，第 $i \\in [2, n]$ 个部门**有且仅有**一个上级部门 $p_i \\in [1, i - 1]$。这样，这家公司的 $n$ 个部门可以视为一个以 $1$ 为根的树。如果 $i$ 是 $j$ 子树中的点，那么称部门 $i$ 是部门 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9168"},"statements":[{"statement_type":"Markdown","content":"众所周知，一个公司的 $n$ 个部门可以组织成一个树形结构。形式化地，假设这些部门依次编号为 $1, \\ldots, n$，那么除了 $1$ 号部门以外，第 $i \\in [2, n]$ 个部门**有且仅有**一个上级部门 $p_i \\in [1, i - 1]$。这样，这家公司的 $n$ 个部门可以视为一个以 $1$ 为根的树。如果 $i$ 是 $j$ 子树中的点，那么称部门 $i$ 是部门 $j$ 的子部门。\n\n该公司初始时有 $k$ 名优秀员工，编号依次为 $1 \\ldots k$。第 $i$ 名优秀员工初始时在第 $x_i$ 个部门工作，并且其有一个能力值 $v_i > 0$。\n\n为了最大化公司的运作效率，公司老板 0/\\\\/\\G 决定进行一些人员调动。具体来说，可以将编号为 $i$ 的优秀员工调动到 $x_i$ 的一个子部门，或者不调度（此时该员工在 $x_i$ 部门）。随后，优秀员工们会在其所在的部门竞选部门领导——能力值最高者将担任这一职位，并给公司带来等同于其能力值的贡献。如果一个部门一个优秀员工也没有，那么就无法选出部门领导，从而对公司的贡献将是 $0$。此时，公司的业绩被定义为公司各部门的贡献之和。\n\n公司老板 0/\\\\/\\G 自然想知道，该如何进行人员调动，使公司的业绩最大？\n\n这当然难不倒他，然而，公司优秀员工的数量也会发生变化；具体来说，会依次发生 $m$ 个事件，每个事件形如：\n\n- `1 x v`：先令 $k = k + 1$，然后新增一位编号为 $k$、初始部门为 $x$、能力值为 $v$ 的优秀员工；\n- `2 id`：编号为 $\\mathit{id}$ 的优秀员工将被辞退。\n\n公司老板 0/\\\\/\\G 希望你能在最开始和每个事件发生后，告诉他公司的业绩最大可能是多少？\n\n注意，每次人员调动都是独立的，也就是每次计算公司的最大可能业绩时，每个优秀员工都会回到其所在的初始部门。\n\n## Input\n\n输入的第一行包含一个正整数 $\\mathit{sid}$，表示该测试点对应的数据范围以及特殊性质，详见后表；\n\n输入的第二行包含三个整数 $n, k, m$，分别表示部门数，初始优秀员工数和事件数。\n\n输入的第三行包含 $n - 1$ 个正整数 $p_2, \\ldots, p_n$，表示每个部门的上级部门。\n\n接下来 $k$ 行，每行包含两个正整数 $x_i, v_i$，表示优秀员工的初始部门和能力值。\n\n接下来 $m$ 行，每行形如 `1 x v` 或 `2 id` 表示一次事件。\n\n## Output\n\n输出一行包含 $m + 1$ 个由单个空格隔开的非负整数，依次表示最开始和每个事件发生后，公司的业绩可能的最大值。\n\n[samples]\n\n## Background\n\n**滥用本题评测将封号**。\n\n## Note\n\n**【数据范围】**\n\n对于所有的数据，保证：$1 \\le \\mathit{sid} \\le 15$，$1 \\le n, k \\le 10^5$，$0 \\le m \\le 10^5$，$1 \\le p_i < i$，$1 \\le x_i, x \\le n$，$1 \\le v_i, v \\le 10^5$。\n\n对于事件 2，保证：$1 \\le \\mathit{id} \\le k$ 且编号为 $\\mathit{id}$ 的员工在此事件发生时仍在工作。\n\n|测试点编号|$\\mathit{sid}$|$n \\le$|$k \\le$|$m \\le$|特殊性质|\n|:-:|:-:|:-:|:-:|:-:|:-:|\n|1|$1$|$6$|$6$|$6$|无|\n|2, 3|$2$|$9$|$6$|$6$|无|\n|4, 5|$3$|$16$|$66$|$66$|无|\n|6 ~ 8|$4$|$66$|$66$|$0$|无|\n|9 ~ 11|$5$|$2,333$|$2,333$|$0$|无|\n|12 ~ 14|$6$|$10^5$|$10^5$|$0$|B|\n|15 ~ 18|$7$|$10^5$|$10^5$|$0$|无|\n|19 ~ 21|$8$|$2,333$|$2,333$|$2,333$|A|\n|22 ~ 24|$9$|$10^5$|$10^5$|$10^5$|AB|\n|25 ~ 28|$10$|$10^5$|$10^5$|$10^5$|A|\n|29 ~ 31|$11$|$2,333$|$2,333$|$2,333$|无|\n|32 ~ 34|$12$|$10^5$|$10^5$|$10^5$|C|\n|35 ~ 38|$13$|$10^5$|$10^5$|$10^5$|B|\n|39 ~ 44|$14$|$66,666$|$66,666$|$66,666$|无|\n|45 ~ 50|$15$|$10^5$|$10^5$|$10^5$|无|\n\n特殊性质 A：无事件 2；\n\n特殊性质 B：$p_i = i - 1$；\n\n特殊性质 C：$v_i = v = 1$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9168","tags":["各省省选","2023","O2优化"],"sample_group":[["1\n3 2 1\n1 1\n2 1\n1 3\n1 2 2\n","4 5\n"],["见附件中的 transfer/transfer2.in","见附件中的 transfer/transfer2.ans"],["见附件中的 transfer/transfer3.in","见附件中的 transfer/transfer3.ans"],["见附件中的 transfer/transfer4.in","见附件中的 transfer/transfer4.ans"],["见附件中的 transfer/transfer5.in","见附件中的 transfer/transfer5.ans"],["见附件中的 transfer/transfer6.in","见附件中的 transfer/transfer6.ans"],["见附件中的 transfer/transfer7.in","见附件中的 transfer/transfer7.ans"],["见附件中的 transfer/transfer8.in","见附件中的 transfer/transfer8.ans"],["见附件中的 transfer/transfer9.in","见附件中的 transfer/transfer9.ans"],["见附件中的 transfer/transfer10.in","见附件中的 transfer/transfer10.ans"],["见附件中的 transfer/transfer11.in","见附件中的 transfer/transfer11.ans"],["见附件中的 transfer/transfer12.in","见附件中的 transfer/transfer12.ans"],["见附件中的 transfer/transfer13.in","见附件中的 transfer/transfer13.ans"],["见附件中的 transfer/transfer14.in","见附件中的 transfer/transfer14.ans"],["见附件中的 transfer/transfer15.in","见附件中的 transfer/transfer15.ans"]],"created_at":"2026-03-03 11:09:25"}}