题目描述

公司A的服务器有一种结构，其中 $N$ 台设备编号为 $1, 2, ..., N$，通过 $N-1$ 条电缆连接在一起。第 $i$ 条电缆连接设备 $U_i$ 和设备 $V_i$。任意两个不同的设备通过一些电缆连接。

每个设备 $v$ ($1 \leq v \leq N$) 都有一个非零整数 $A_v$，表示如下内容：

• 如果 $A_v < 0$，设备 $v$ 是一个消耗电力为 $-A_v$ 的计算机。
• 如果 $A_v > 0$，设备 $v$ 是一个提供电力为 $A_v$ 的电池。

你决定断开一些电缆（可能为零）来禁用服务器。当断开一些电缆时，设备将被分成若干个连通分量。只有当所有这些连通分量满足以下条件之一时，服务器才会被禁用：

• 连通分量中没有计算机。也就是说，属于该连通分量的每个设备 $v$ 都满足 $A_v$ 是正数。
• 连通分量中的电力供应不够。也就是说，属于该连通分量的所有设备 $v$ 上的 $A_v$ 的总和是负数。

为了禁用服务器，至少需要断开多少根电缆？

约束条件

• $1 \leq N \leq 5000$
• $1 \leq |A_i| \leq 10^9$ ($1 \leq i \leq N$)
• $1 \leq U_i, V_i \leq N$ ($1 \leq i \leq N-1$)
• $U_i \neq V_i$ ($1 \leq i \leq N-1$)
• 任意两个不同的设备通过一些电缆连接。
• 输入中的所有值都是整数。

---

输入

从标准输入读入输入数据，输入格式如下：

$N$ $A_1$ $A_2$ $...$ $A_N$ $U_1$ $V_1$ $U_2$ $V_2$ : $U_{N-1}$ $V_{N-1}$

输出

输出答案。

---

示例输入1

7
-2 7 5 6 -8 3 4
1 2
2 3
2 4
1 5
5 6
5 7

示例输出1

1

我们应该断开连接设备 $1$ 和设备 $2$ 的电缆。

---

示例输入2

4
1 2 3 4
1 2
1 3
1 4

示例输出2

0

---

示例输入3

6
10 -1 10 -1 10 -1
1 2
2 3
3 4
4 5
5 6

示例输出3

5

---

示例输入4

8
-2 3 6 -2 -2 -5 3 2
3 4
7 6
6 2
8 2
5 3
1 8
3 7

示例输出4

3

---

示例输入5

10
3 4 9 6 1 5 -1 10 -10 -10
7 4
5 6
8 1
9 5
7 1
10 3
2 8
4 10
9 2

示例输出5

3