分数: 600 点
问题陈述
A 公司的服务器的结构如下 N 设备编号 1, 2, ..., N 与 N - 1 电缆。 的 i-th 电缆连接设备 U_i 和设备 V_i。 任何两个不同的设备都通过一定数量的电缆连接。
每个设备 v (1 \leq v \leq N) 有一个非零整数 A_v,代表以下内容:
- If A_v < 0,设备 v 是一台消耗电力的计算机 -A_v.
- If A_v > 0,设备 v 是提供电力的电池 A_v.
您已决定断开一定数量的电缆(可能为零)以禁用服务器。 当某些电缆断开时,设备将分为一定数量的连接组件。 如果所有这些连接的组件满足以下条件之一,服务器将被禁用:
- 连接的组件中没有计算机。也就是说, A_v 对于每台设备都是积极的 v 属于连通分量。
- 连接的组件中电力供应不足。也就是说,总和 A_v 在所有设备上 属于连通分量的 v 为负。
至少需要断开多少根电缆才能禁用服务器?
约束
- 1 \leq N \leq 5 000
- 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