[IOI2014]friend朋友

时间限制:5s      空间限制:16MB

题目描述

我们建立了一个由编号为0, ... ,n-1的n个人组成的社交网络。网络中的有些对会成为朋友。如果X号人成为Y号人的朋友,则Y号人同时也会成为X号人的朋友。
这些人将通过n个阶段加入这个网络,阶段也编号为0至n-1。第i号人在第i个阶段加入。在阶段0,0号人加入网络并成为唯一的人。此后n-1个阶段的各个阶段,都有一个人会被主持人加入到网络中,而这个主持人可以是已在网络中的任何一个人。在阶段i中 (0<i<n),该阶段的主持人可以用如下三种方式之一把第 号人加入到网络中:
1.IAmYourFriend 将第i号人仅变成主持人的朋友。
2.MyFriendsAreYourFriends 将第i号人变成主持人当前的每一个朋友的朋友。 注意,这个方式不会将第i号人变成主持人的朋友。
3.WeAreYourFriends 将第i号人变成主持人的朋友,同时也变成主持人当前的 每一个朋友的朋友。
在建立此网络之后,我们想挑选一个调查的样本,也就是说要从网络中选择一组人。由于朋友之间通常拥有相似的兴趣,因此样本不应包含任何一对互为朋友的人。每个人都会有一个调查的可信度,表示为一个正整数,而我们想要找出一个可信度总和最大的样本。


输入格式

第 1 行: n
第 2 行: confidence[0], ..., confidence[n-1]
第 3 行: host[1], protocol[1], host[2], protocol[2], ..., host[n-1], protocol[n-1]
n: 人数.
confidence: 大小为n的数组;confidence[i]表示第i号人的可信度。
host: 大小为n的数组;host[i] 表示阶段i的主持人。
protocol: 大小为n的数组;protocol[i] 表示在阶段i(0<i<n)所采用的方式的代码: 0 代表 IAmYourFriend, 1 代表 MyFriendsAreYourFriends, 而 2 代表WeAreYourFiends。


输出格式

输出一个整数表示样本可信度总和的最大值。


样例输入

6
13 3 6 20 10 15
0 0 0 1 1 2 2 1 0 0

样例输出

35

提示


题目来源

鸣谢yts1999上传