#2422. 最大权独立集问题

    ID: 2422 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest927来源:qoj.ac数据:公开样例树形DP深搜

最大权独立集问题

最大权独立集问题

题目描述

NOI2022 省选 DAY2 最大权独立集问题(mis) 最大权独立集问题(mis) 【题目描述】 小E 喜欢出最大权独立集问题。 接下来,他还想了n 道最大权独立集问题。 小E 有n 个AI,编号为1 ∼n 。 开始时第i 个AI 里面存有di 道小E 事先出好的最大权独立集问题。 有些AI 之间可以互相通信,对于所有的2 ≤i ≤n ,第i 个AI 可以和第ci 个AI 互相通信。其中ci < i,且相同的ci 出现不超过2 次。所以,这些AI 连成了一个二叉 树的形状。此外,其他对AI 不可以互相通信。 小E 需要暂时断开这些AI 之间的连接。他只能逐一断开AI 之间的连接。两个原 本能够互相通信的AI 在断开它们之间的连接之前,会互相交换存在里面的所有题目, 具体请见样例。 小E 希望在断掉所有连接之后,参与交换的题目数量最少。 他想叫你帮他解决这个问题,还说如果你成功解决了这个问题,那么在出那些最大 权独立集问题的时候,他会帮你提交一份标程代码。 【输入格式】 从文件mis.in 中读入数据。 第一行一个正整数n。 第二行n 个整数,第i 个表示di。 第三行n −1 个正整数,第i 个表示ci+1。 【输出格式】 输出到文件mis.out 中。 一行一个整数表示答案。 【样例1 输入】 1 3 2 2 1 3 3 1 1 【样例1 输出】 1 7 第7 页 共8 页

NOI2022 省选 DAY2 最大权独立集问题(mis) 【样例1 解释】 一种最优的方案是:断开1 号与2 号AI 之间的连接,这样需要交换2 + 1 = 3 道 题;然后断开1 号与3 号AI 之间的连接,这样需要交换1 + 3 = 4 道题。所以答案是7。 【子任务】 保证1 ≤ci < i,且相同的ci 最多出现2 次。 保证1 ≤di ≤109。 测试点编号 n ≤ 1 ∼3 10 4 ∼7 100 8 ∼11 500 12 ∼16 1000 17 ∼25 5000 第8 页 共8 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
2 1 3
1 1
7