题目描述

TOJ 1039

修罗王欲瘫瘓天顶星人军队的建制，于是设计邀请天顶星人军官在一个城堡参加一场 盛大的晚会。他的借口是为了让到会的每个人不受他的直接上司约束而能玩得开心,所以 晚会的安排是:如果邀请了某个人,那么一定不会再邀请他的直接的上司,但该人的上司的 上司，上司的上司的上司......都可以邀请。已知每个人最多有唯一的一个上司。

已知每个参加晚会的天顶星人都有一定的价值,求一个邀请方案,使价值的和最大。

输入格式

第$\red{1}$行一个整数$\red{N(1≤}$$\red{N≤}$$\red{6 000)}$表示天顶星人的人数。

接下来$\red{N}$个整数。表示第$\red{i}$个人的价值$\red{x(- 128≤}$$\red{x≤}$$\red{127)}$。

接下来每行两个整数$\red{L,K}$。表示第$\red{K}$个人是第$\red{L}$个人的上司。 输入以$\red{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