树

题号：NC212400
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

_{一颗有n个节点根树，根为1，每个节点有一个整数权值}

_{操作1：选择一个节点 x,}_让 $v_{x}$ _加上k,_同时x_{的每一个儿子（注意这里是儿子而非子树）都减去k（} k $\in$ _Z）

_{特别的，对于一个叶子结点x没有儿子，即可以让x加上任意整数}

操作2：让根节点加上任意整数k

_{问最少经过几次操作可以使每个节点上的数都大于等于0}

第一行包含一个正整数n，表示n个节点

第二行包含n个整数，第i个数表示 $v_{i}$

接下来n-1行每行2个数x，y，表示有xy之间的一条边相连（不保证x为y的父亲）

输出文件共一行一个整数，表示操作的最小次数

示例1

复制

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

复制

示例2

复制

14
901 234 80 268 28 -550 -850 2 829 -436 -764 -620 2 820 
12 4
4 2
2 11
11 13
13 3
3 1
1 8
8 7
7 5
5 14
4 6
7 9
1 10

复制

给1号节点-100000同时3,8,10号节点+100000
给8号节点-1000同时7号节点+1000
给3号节点-1000同时13号节点+1000
给13号节点-1000同时11号节点+1000
给12号节点+1000，他没有儿子
给6号节点+1000，他没有儿子

对于30%的数据：n<=100
对于45%的数据：n<=1000
对于100%的数据：n<=200000，<
保证中间所有运算均不超过long long