题目描述

Ural 大学有 $N$ 名职员，编号为 $1 \sim n$。

他们的关系就像一棵以 $1$ 号点为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 $H_i$ 给出。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行输入一个整数 $N$。$(1\le N\le 5000)$

接下来一行输入 $N$ 个正整数，表示 $H_i$。$(-100\le H_i\le 100)$

接下来 $N-1$ 行，每行输入一对整数 $a,b$，表示 $b$ 是 $a$ 的上司。$(1\le a,b\le N)$

输出格式

输出最大的快乐指数。

样例输入

6
1 4 7 8 -6 3
4 1
3 4
2 3
6 3
5 3

样例输出

15