给定一棵树 T ，树 T 上每个点都有一个权值。 定义一颗树的子链的大小为：这个子链上所有结点的权值和 。 请在树 T 中找出一条最大的子链并输出。
输入描述:
第一行输入一个 。接下来一行包含n个数，对于每个数 ，表示 i 结点的权值。接下来有n-1行，每一行包含两个数u，v（  , u != v），表示u与v之间有一条边。


输出描述:
仅包含一个数，表示我们所需要的答案。
示例1

输入

5
2 -1 -1 -2 3
1 2
2 3
2 4
2 5

输出

4

说明

样例中最大子链为1 -> 2 -> 5

备注:
一个结点，也可以称作一条链
加载中...