树形DP初步-真树

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 167 总提交人数: 170

题目描述

新年到了,白兔家族要搞大大的聚会。但是并不是每只白兔都是同一辈分的,于是便有一棵以老白兔为根的家族树。

每只白兔都有它们自己唯一的整数编号(范围在1到N之间),并且对应一个参加聚会所得的开心值。为了使每个参加聚会的白兔都巨开心,老白兔想让每只白兔和他的上一代白兔不会同时参加聚会。

求参加聚会的白兔获得的最大总开心值。

输入

输入的第一行是一个整数N,1<= N <= 6000

以下的N行是对应的N个白兔的开心值(开心值是一个从-128到127之间的整数)

接着是白兔的家族树,树的每一行格式如下: 每行输入一对整数L,K。表示第K个白兔是第L个白兔的上一代。 输入以0 0表示结束

输出

参加聚会的白兔获得的最大总开心值

输入样例

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

输出样例

5

相关推荐