#6355. 「CodePlus 2018 4 月赛」Tommy 的结合

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

深邃的天空仿佛要吞噬一切,一场 Codeforces 比赛刚刚结束。“怎么还不理我……”,睡眼惺忪的 Tommy 拿起盖在一旁的手机。空空荡荡的 QQ 提示框,没有一丝的温度。Tommy 叹了口气。昏黄的灯发出微弱的光芒,抚摸着呼呼作响的电脑。

桌面上堆满了写满 \partial \int 的草稿纸,手机闪光灯自制的简易台灯发出刺眼的白光;灯火缱绻,映照一双如画倦容。十几个 DDL 就在附近,QQ 那边的人已经三天三夜没有合眼了。这是 Tommy 所不知道的事。


人生大概就是这样。在这物欲横流的红尘紫陌中,芸芸众生为了生计四处奔走,交谈越来越少,感情越来越淡。但是,著名科学家 Access Globe 的最新研究成果可以解决这样的问题:通过增加同时做的事情来增加共同语言。

A 和 B 都得到了一些任务,设他们要执行的任务集合分别为 V_A V_B 。对每个人来说,任务 1 是必须一开始做的,而其他的每个任务 e 都存在一个前置任务 p_e ,表示任务 e 必须在任务 p_e 完成后才能执行。也就是说,每个人的任务的依赖关系构成了一棵有根外向树,一个任务 e 能被执行当且仅当 p_e,p_{p_{e}},...,1 这些任务全部都被执行,称 p 依赖任务 p_e,p_{p_{e}},...,1

现在,A 和 B 希望他们能有一些任务是共同完成的,因此他们决定这样选出一些任务:A 选出 m 个任务 a_1,...,a_m ,要求 a_1=1 ,并且对于任意的 1\le i<m ,都要求 a_{i+1} 依赖任务 a_i ;同时 B 也选出 m 个满足同样要求的任务 b_1,...,b_m ,这样,A 就可以沿着从 1 A_m 的路径依次执行这些任务,同时 B 也可以沿着 1 B_m 的路径依次执行这些任务;并且经过安排,当 A 在执行任务 a_i 的时候,B 恰好在执行任务 b_i ,在这时 A 和 B 就能取得联系,增进感情。

模型的目标为最大化亲密度。对于一组同时执行任务的关系 a_i b_i ,可以获得 C_{a_i,b_i} 的得分;同时, A B 一旦失去联系,就会使得亲密度降低,在每一分钟,如果一方距离上次和对方联系后已经执行任务 i 分钟,就会使得亲密度降低 2i-1

例如,两个人要做的任务所花费的时间分别为 2,1,4,7 4,8,3,6,4 ,并且共同完成了第一个任务和最后一个任务,那么 A 在执行中间两个任务的 1+4=5 分钟没有和 B 联系,使得亲密度降低 1+3+...+11=25 ;同时 B 在执行中间三个任务的 8+3+6=17 分钟没有和 A 联系,使得亲密度降低 1+3+...+35=289 。注意,亲密度的计算只和任务执行的时间有关;并且任意两个任务都可以作为 a_i b_i 同时执行,不需要保证它们花费的时间相同。

现在,给出 A 和 B 的任务、依赖关系和每个任务的执行时间,请你帮我们求出能够获得的最大的亲密度。

输入格式

从标准输入读入数据。

第一行两个整数 |V_A|,|V_B|

第二行 |V_A|-1 个整数 t^{(a)}_{2},t^{(a)}_{3},...,t^{(a)}_{|V_A|} ,表示 A 的每个任务的时间长度;

第三行 |V_B|-1 个整数 t^{(b)}_{2},t^{(b)}_{3},...,t^{(b)}_{|V_B|} ,表示 B 的每个任务的时间长度;

第四行 |V_A|-1 个整数 p^{(a)}_{2},p^{(a)}_{3},...,p^{(a)}_{|V_A|} ,表示 A 的每个任务的前置任务,保证 p^{(a)}_{i}< i

第五行 |V_B|-1 个整数 p^{(b)}_{2},p^{(b)}_{3},...,p^{(b)}_{|V_B|} ,表示 B 的每个任务的前置任务,保证 p^{(b)}_{i}< i

接下来 |V_A|-1 行,每行 |V_B|-1 个整数,第 i-1 行第 j-1 列为 C_{i,j} ,表示 A 和 B 同时分别执行对应的任务 i, j 能获得的亲密度,注意这些亲密度不一定是非负的;

注意以上输入均不包括第 1 个任务的信息,因为它和亲密度的计算没有关系。

输出格式

输出到标准输出。

输出能获得的最大的亲密度。

样例

样例输入

5 4
2 1 2 1
1 1 1
1 2 3 4
1 2 2
-8 -1 6
4 -3 7
-7 5 5
-7 5 -5

样例输出

5

样例解释

A 和 B 分别选出任务 1,3,4 1,2,3 ,同时执行的任务对 (1,1) (3,2) (4,3) 使得他们获得了 4+5=9 的亲密度;A 孤独地执行任务 2 2 分钟丢失了 1+3=4 的亲密度,因此最终的总亲密度为 9-4=5 。这就是亲密度最大的方案。

数据范围与提示

子任务 分值 \|V_A\|,\|V_B\|\le C_{i,j}\ge 0 ? p^{(a)}_i=p^{(b)}_i=i-1 ?
1 7 66
2 13 666
3 8
4 16
5 18 2,666
6 14
7 24

对于所有数据, 2\le |V_A|,|V_B|\le 2,666 1\le t^{(a)}_i,t^{(b)}_i\le 1,206 0\le |C_{i,j}|\le 2,017,011,328


来自 CodePlus 第 4 次月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea 与命题/陈俊锟 验题/Tommy > <
Git Repo:https://git.thusaac.org/publish/CodePlus4
感谢腾讯公司对此次比赛的支持。