题目描述

小明想要抽笔，由于它只有无限元，而每支笔都要十元，每支笔有他能给小明的价值（可能为负数（看着就恶心）），这些笔的摆放方式就是一棵树，每支笔可以选择抽或者不抽，但是如果他的父亲笔抽了，这支笔就不能抽了。

输入格式

第一行一个数 $n$ ，表示有 $n$ 支笔。 第二行 $n$ 个数，表示有这支笔带给他的价值。 下面 $n-1$ 行（懒得写了，反正就是构建一棵树）。

输出格式

一行一个数，表示最高的情绪价值。

7
1 1 1 1 1 1 1
1 3
2 3
6 4
7 4
4 5
3 5

5

数据规模与约定

提示 数据规模与约定 对于 100% 的数据，保证 1 ≤ n ≤ 6×10^3^，−128 ≤ 价值 ≤ 127，且给出的关系一定是一棵树。