题目描述

小华对植物学充满热情，总是在课后留在温室向园艺师傅请教问题。一天她在校园散步时，看到一位老园丁正在修剪花丛，顿时想到了一个有趣的数学问题。

一株奇特的盆景，上面共有 $n$ 朵花，通过 $n-1$ 条枝干彼此相连（未修剪时任意两朵花之间都连通）。每朵花有一个「观赏价值」，正值表示赏心悦目，负值则令人不快。

所谓「修剪」，就是剪掉一条枝干，盆景分成两株，丢弃其中一株。经过若干次修剪后，只剩下一株（也可能只是一朵花）。

请通过若干次修剪（也可以不修剪），使剩余那株盆景上所有花朵的观赏价值之和最大。

输入格式

第一行一个整数 $n$（$1\le n\le 16000$），表示盆景上花朵的总数。

第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 朵花的观赏价值。

接下来 $n-1$ 行每行两个整数 $a, b$，表示存在一条连接第 $a$ 朵花和第 $b$ 朵花的枝干。

输出格式

一个整数，表示修剪后所能得到的观赏价值之和的最大值。保证绝对值不超过 $2147483647$。

样例

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

3

提示

数据范围及约定

• 对于 $60\%$ 的数据，有 $1\le n\le 1000$；
• 对于 $100\%$ 的数据，有 $1\le n\le 16000$。