/ JF_OIer / 题库 /

舞会

舞会

测试数据来自 system/1706

描述

Arthur公司是一个等级森严的公司,它们有着严格的上司与下属的关系,公司以总裁为最高职位,他有若干个下属,他的下属又有若干个下属,他的下属的下属又有若干个下属……现接近年尾,公司组织团拜活动,活动中有一部分是自由舞会,公司的每个职员都有一个搞笑值,现要你制定一套哪些人上台的方案,使得台上所有演员的搞笑值最大。当然,职员们是不会和他们的顶头上司一起上台的。

格式

输入格式

第一行一个整数N,表示这个公司总共的职员个数。

接下来一行有N个整数,由空格隔开,第i个整数表示职员i的搞笑值Ai(-1327670≤Ai≤1327670)。

接下来N-1行,每行一个1到N的整数,第i个整数表示职员i+1的顶头上司是谁,当然总裁就是职员1。

输出格式

一个整数,表示台上所有职员搞笑值之和的最大值。

样例1

样例输入1

7
1 1 1 1 1 1 1
1
1
5
1
4
4

样例输出1

5

提示

【数据范围】
保证100%的数据N≤5000

来源

URAL 由xzx改编

信息

ID
1002
难度
2
分类
动态规划 | 树形DP 点击显示
标签
递交数
3
已通过
2
通过率
67%
上传者