当前没有测试数据。

题目描述

一棵树，要求每个叶子的美丽程度都是他叶子节点的总和（但是可以减掉子节点），根是 1 号节点，求根节点最大的美丽程度。 每个点上都有一堆石头，从根节点到叶子节点这条路上的所有石头堆组成的一个序列，将序列里两个相邻的石头堆合并可以得到这两个石头堆的质量和（可能是负数）。 叶子节点求出的这个质量和就会向上传递美丽程度。

输入格式

第一行，一个数 $n$ 表示有n个节点。 第二行， $n$ 个数，表示每个结点的石头堆的质量。 后面 n-1 行，描述一棵树。

输出格式

根节点最大的美丽指数。

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

3

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 100$。