年会

题目描述

背景

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

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

输入格式

第1行是一个整数N. 1 ≤ N ≤ 6000.

接着的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