/ Vijos / 题库 /

舞会

舞会

描述

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
1706
难度
6
分类
动态规划 | 树形DP 点击显示
标签
(无)
递交数
1375
已通过
380
通过率
28%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

湖南师大附中练习赛