← 返回题目列表

AtCoder · aising2019_e

E. 对树的攻击

中文机器翻译题面 查看原题

分数: 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