题目描述

有一个派对即将举行，以庆祝乌拉尔国立大学（Ural State University）成立$80$周年。这所大学的员工之间存在层级关系，这意味着上下级关系构成了一棵以校长$V. E. Tretyakov$为根的树。为了让派对充满乐趣，校长不希望一个员工和他（或她）的直接上级同时出现在派对上。人事部门为每位员工评估了活跃度，因此每个人都对应一个评分（可以为负）。你的任务是列出一份宾客名单，使得宾客的活跃度评分之和最大。

输入格式

员工编号从$1$到$N$。第一行输入一个整数$N$，满足$1 \leq N \leq 6000$。接下来的$N$行，每行包含对应员工的活跃度评分。评分是一个整数，范围在$-128$到$127$之间。然后是$N - 1$行，用于描述上下级关系树。每行关系的格式为：

$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

输出数据 1

5

题目来源

Ural State University Internal Contest October'2000 Students Session