题目描述

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

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

输入格式

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

输出格式

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

样例 1

输入

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

输出

5

题目来源：吉首大学软件学院；FPS 共享题包，题包内第 104 题。保留原作者与原赛事署名。