题目描述

给定一棵包含 $n$ 个节点的无向树，每个节点有一个权值 $a_i$（有正有负）。要求在树中选出一个连通子图（即一棵子树），使得这棵子树包含的节点权值之和最大。

输入格式

第一行一个整数 $n\ (1\le n\le 16000)$。表示树的结点数

第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个节点的权值。

接下来 $n-1$ 行每行两个整数 $a,b$，表示存在一条连接第 $a$ 个节点和第 $b$ 个节点的无向边。

输出格式

一个数，表示树中所有子树权值和中的最大权值和。

样例输入1

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

样例输出1

3

说明

数据范围

• 对于 $60\%$ 的数据，有 $1\le n\le 1000$；
• 对于 $100\%$ 的数据，有 $1\le n\le 16000，-10^9\le a_i\le10^9$。