bzoj#P4458. GTY 的 OJ
GTY 的 OJ
题目描述
身为 IOI 金牌的 gtyzs 有自己的一个 OJ,名曰 GOJ。GOJ 上的题目可谓是高质量而又经典,他在他的 OJ 里面定义了一个树形的分类目录,且两个相同级别的目录是不会重叠的。比如图论的大目录下可能分为最短路,最小生成树,网络流等低一级的分类目录,这些目录下可能还有更低一级的目录,以此类推。现在 gtyzs 接到了一个任务,要他为 SDTSC 出题。
他准备在自己的 OJ 题库中找出 道题作为 SDTSC 的试题,而他深知 SDTSC 的童鞋们个个都是神犇,所以 gtyzs 认为自己出的这 道题中,每道题都应该属于不少于 种分类目录;可他又怕自己的题没有人会做,所以每道题也应该属于不超过 种分类目录,并且这些分类目录应该是连续的,不能出现断层。对了,最重要的是,不存在一道题,它属于两个分类目录且这两个目录不是包含关系。(比如不存在一道题它既是一道 DP 题,又是一道网络流题)gtyzs 怕被骂,所以他希望不存在任意的一对题目 ,使得 所属的分类目录与 完全相同。举例来说,gtyzs 不能出两道同样的都是动态规划,背包的题,但是却可以出一道属于动态规划,背包和 01 背包的题和一道属于背包,01 背包的题,当然也可以出一个属于图论的题和一个属于数论的题。(注意:一道题所属的分类目录不一定从根开始,如加粗部分所示)。
为了让自己的题目变得更加靠谱,他给每一个分类目录都定了一个靠谱值 ,这个值可正可负。一道题的靠谱度为其从属的分类目录靠谱值的加和。我们假设动态规划的靠谱值为 ,插头DP的靠谱值为 ,则一道动态规划插头 DP 的题的靠谱值就是 。gtyzs希望自己出的这 道题,在满足上述前提条件下,靠谱度总和最大。gtyzs 当然会做啦,于是你就看到了这个题。
输入格式
输入的第一行是一个正整数 ,代表分类目录的总数。
接下来的一行,共 个正整数,第 个正整数为 ,表示分类目录 被 所包含。保证一个分类目录只会被一个分类目录所包含,且包含关系不存在环。特别的, 表示它是根节点,我们保证这样的点只存在一个。
接下来的一行,共 个整数,第 个数表示 。
最后一行,三个正整数 。
为了方便,所有的测试数据中都有 ,且对于任意的 ,有 。
输出格式
一行一个整数,表示最大的靠谱度。
7
0 1 1 2 2 3 3
2 3 4 1 2 3 4
3 3 3
26
样例解释
对于样例数据,gtyzs 选择这样的 道题: 属于分类目录 , 属于分类目录 , 属于分类目录 。这三道题是满足要求的能取得最大靠谱度 的试题 题解:下载链接 By jinlifu1999。
数据规模及约定
对于 的数据,,,。 保证输入数据有解。
题目来源
By jinlifu1999