Problem1399--年会

1399: 年会

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

背景
某大学校长准备开一次年会. 该校的员工具有等级结构, 即师生关系构成一棵树, 以校长为树根. 员工号是1到N之间的整数. 人事部门把所有员工按活跃度排序. 为了让年会使所有参加者都玩的高兴, 校长不想让任何一个员工和他/她的直接导师同时被邀请.

你的任务是列一张客人名单, 以使客人活跃度最大.

Input

第1行是一个整数N. 1 ≤ N ≤ 6000.
接着的N行包含相应员工的活跃度.活跃度是一个-128到127之间的整数.
其后是师生关系表. 每行有如下形式:
L K
表示第K个员工是第L个的直接导师.
输入以
0 0
结束.

Output

输出是客人最大总活跃度.

Sample Input Copy

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

Sample Output Copy

5

Source/Category