Problem 5261 --没有上司的晚会--树型动态规划训练T5

5261: 没有上司的晚会--树型动态规划训练T5

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 7  Solved: 5
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][284kb]

Description

没有上司的晚会(party.pas/c/cpp)

 

背景 

有个公司要举行一场晚会。

为了能玩得开心,公司领导决定:如果邀请了某个人,那么一定不会邀请他的上司

(上司的上司,上司的上司的上司……都可以邀请)。

题目

每个参加晚会的人都能为晚会增添一些气氛,求一个邀请方案,使气氛值的和最大。

输入格式

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


Input

Output

HINT

Source

[Submit][Status]