问题 5934 --【树形动态规划】没有上司的晚会

5934: 【树形动态规划】没有上司的晚会

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 2
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][352kb]

题目描述

 

LA有个公司要举行一场晚会。为了能玩得开心,LA决定:如果邀请了某个人,那么一定不会邀请他的上司(上司的上司,上司的上司的上司……都可以邀请)。每个参加晚会的人都能为晚会增添一些气氛,求一个邀请方案,使气氛值的和最大。所有员工的编号为1N

输入

 

多组数据!!!!!!!!!

 

1行一个整数N1<=N<=6000)表示公司的人数。

接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)

接下来每行两个整数LK。表示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

提示

来源

 

[提交][状态]