Score : 600 points
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:
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:
At least how many cables do you need to disconnect in order to disable the server?
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}
Print the answer.
7 -2 7 5 6 -8 3 4 1 2 2 3 2 4 1 5 5 6 5 7
1
We should disconnect the cable connecting Device 1 and Device 2.
4 1 2 3 4 1 2 1 3 1 4
0
6 10 -1 10 -1 10 -1 1 2 2 3 3 4 4 5 5 6
5
8 -2 3 6 -2 -2 -5 3 2 3 4 7 6 6 2 8 2 5 3 1 8 3 7
3
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
3