9084: 树上子链
[Creator : ]
Description
给定一棵树 T ，树 T 上每个点都有一个权值。
定义一颗树的子链的大小为：这个子链上所有结点的权值和。
请在树 T 中找出一条最大的子链并输出。
一个结点，也可以称作一条链。
定义一颗树的子链的大小为：这个子链上所有结点的权值和。
请在树 T 中找出一条最大的子链并输出。
一个结点，也可以称作一条链。
Input
第一行输入一个 $n\ (1 \le n \le 10^5)$。
接下来一行包含 $n$ 个数，对于每个数 $a_i\ (-10^5 \le a_i \le 10^5)$，表示 $i$ 结点的权值。
接下来有 $n-1$ 行，每一行包含两个数 $u,v\ (1≤u,v≤n,\ u != v)$，表示 $u$ 与 $v$ 之间有一条边。
Output
仅包含一个数，表示我们所需要的答案。
Sample 1 Input
5
2 -1 -1 -2 3
1 2
2 3
2 4
2 5
Sample 1 Output
4
样例中最大子链为 $1 \to 2 \to 5$。