E - Attack to a Tree 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

A 社のサーバーは 1, 2, ..., N の番号がついた N 個のデバイスを N - 1 本のケーブルで接続した構造をしています。 i 本目のケーブルはデバイス U_i とデバイス V_i を接続しています。 どの異なる 2 つのデバイスも何本かのケーブルを介して接続されています。

各デバイス v (1 \leq v \leq N) には 0 でない整数 A_v が割り当てられています。 これらの整数は以下のことを表します。

  • A_v < 0 のとき、デバイス v はコンピュータであり、大きさ -A_v の電力を消費することを表す。
  • A_v > 0 のとき、デバイス v はバッテリーであり、大きさ A_v の電力を供給できることを表す。

あなたは何本か (0 本以上) のケーブルを切断することで A 社のサーバーの機能を停止させることにしました。 ケーブルを切断するとデバイスはいくつかの連結成分に分かれます。 これら連結成分がすべて以下のいずれかの条件を満たすようになれば、サーバーは機能を停止します。

  • 連結成分に属する各デバイス v に対する A_v の値がすべて正である。すなわち、連結成分にコンピュータが存在しない。
  • 連結成分に属する各デバイス v に対する A_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)
  • どの異なる 2 つのデバイスも何本かのケーブルを介して接続されている。
  • 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

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

Score : 600 points

Problem Statement

The server in company A has a structure where N devices numbered 1, 2, ..., N are connected with N - 1 cables. The i-th cable connects Device U_i and Device V_i. Any two different devices are connected through some number of cables.

Each device v (1 \leq v \leq N) has a non-zero integer A_v, which represents the following:

  • If A_v < 0, Device v is a computer that consumes an electric power of -A_v.
  • If A_v > 0, Device v is a battery that supplies an electric power of A_v.

You have decided to disconnect some number of cables (possibly zero) to disable the server. When some cables are disconnected, the devices will be divided into some number of connected components. The server will be disabled if all of these connected components satisfy one of the following conditions:

  • There is no computer in the connected component. That is, A_v is positive for every device v that belongs to the connected component.
  • There is not enough supply of electric power in the connected component. That is, the sum of A_v over all devices v that belong to the connected component is negative.

At least how many cables do you need to disconnect in order to disable the server?

Constraints

  • 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)
  • Any two different devices are connected through some number of cables.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

1

We should disconnect the cable connecting Device 1 and Device 2.

Sample Input 2

4
1 2 3 4
1 2
1 3
1 4

Sample Output 2

0

Sample Input 3

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

Sample Output 3

5

Sample Input 4

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

Sample Output 4

3

Sample Input 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

Sample Output 5

3