UOJ Logo Universal Online Judge

UOJ

#739. 【统一省选2022】最大权独立集问题

附件下载 统计

小 E 喜欢出最大权独立集问题。

接下来,他还想了 n 道最大权独立集问题。

小 E 有 n 个 AI,编号为 1n

开始时第 i 个 AI 里面存有 di 道小 E 事先出好的最大权独立集问题。

有些 AI 之间可以互相通信,对于所有的 2in,第 i 个 AI 可以和第 ci 个 AI 互相通信。其中 ci<i,且相同的 ci 出现不超过 2 次。所以,这些 AI 连成了一个二叉树的形状。此外,其他对 AI 不可以互相通信。

小 E 需要暂时断开这些 AI 之间的连接。他只能逐一断开 AI 之间的连接。两个原本能够互相通信的 AI 在断开它们之间的连接之前,会互相交换存在里面的所有题目,具体请见样例。

小 E 希望在断掉所有连接之后,参与交换的题目数量最少。

他想叫你帮他解决这个问题,还说如果你成功解决了这个问题,那么在出那些最大权独立集问题的时候,他会帮你提交一份标程代码。

输入格式

第一行一个正整数 n

第二行 n 个整数,第 i 个表示 di

第三行 n1 个正整数,第 i 个表示 ci+1

输出格式

一行一个整数表示答案。

样例一

input

3
2 1 3
1 1

output

7

explanation

一种最优的方案是:断开 1 号与 2 号 AI 之间的连接,这样需要交换 2+1=3 道题;然后断开 1 号与 3 号 AI 之间的连接,这样需要交换 1+3=4 道题。所以答案是 7

数据范围与提示

保证 1ci<i,且相同的 ci 最多出现 2 次。

保证 1di109

测试点编号 n
13 10
47 100
811 500
1216 1000
1725 5000

时间限制:1s2s

空间限制:2048MB