6782: BZOJ2782:经典游戏

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

 SUPER M是一个很经典的游戏  现在改一下规则  有N个城堡(0到n-1)  每个城堡都有一个KOOPA,注意:有些KOOPA会可能有1个FATHER-KOOPA  公主在最后一个城堡内(N-1)  现在每次只能打一个城堡且必须在T[I]时间内打完(否则游戏结束)  如果(N-1)号城堡打完  游戏结束  如果一个KOOPA至少有2个SON-KOOPA被打败  则必须马上去击败这个KOOPA否则会因为愤怒而做掉公主  现在求  最长游戏时间  


输入格式

若干组数据(<=10) 每组开始一个数N 第二行N个数表示T[I](<=100) 第三行N个数表示FATHER-KOOPA所在城堡编号(-1表示无FATHER-KOOPA)(最后一个数一定为-1) 数据以0结尾  


输出格式

  对于每组数据输出一个数,即最大游戏时间  


样例输入

5 
1 2 3 4 5
4 4 4 4 -1
5
2 2 2 2 2
1 2 3 4 -1
0
 

样例输出

12
10
 

提示

对于100%的数据 n<=100000


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: