内网-1237 舞会

题目描述

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

输入

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

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

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

输出

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

样例输入

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

样例输出

5

题解:这是一道树形dp题,很简单,对于每个人抉择选或不选,如果上司选了,他就不选,反之,可选可不选。

 

代码实现:

 

1 评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注