Fueling the Truck in a Tree

There is a country with n cities numbered from 1 to n. Each city has a gas station with a fuel capacity of \(a_i\) (for city \(i\)). The n cities are connected by \(n-1\) roads forming a tree structure. A truck starting with an empty tank at city \(u\) can refuel up to the limit available at the gas station upon arriving at any city.

In order for the truck to go from city \(u\) to city \(v\) along the unique simple path, it must have a fuel amount that is not less than the distance (i.e. the number of edges) between \(u\) and \(v\) at each departure. More formally, if the unique simple path from \(u\) to \(v\) is \(u=x_0,x_1,\dots,x_k=v\), then if the truck’s fuel amount before traversing the edge from \(x_i\) to \(x_{i+1}\) is \(f_i\), the journey is feasible if and only if:

\[ f_0=a_{x_0}, \quad f_i \ge 1 \text{ for } 0\le i< k, \quad f_{i+1}=f_i -1 + a_{x_{i+1}}, \quad \text{and } f_i \ge 0 \text{ for all } i. \]

Note that if \(u=v\), the journey is trivially possible. Your task is to count the number of ordered pairs \((u, v)\) such that a truck starting from \(u\) with an empty tank can reach \(v\) following the rules above.

inputFormat

The first line contains an integer \(n\) \((1 \le n \le 2000)\) representing the number of cities.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((0 \le a_i \le 10^9)\) representing the fuel available at each city.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le n\)) describing an undirected road connecting cities \(u\) and \(v\).

outputFormat

Output a single integer --- the number of ordered pairs \((u,v)\) such that a truck starting from city \(u\) with an empty tank can successfully reach city \(v\) following the rules. Note that \(u\) may be equal to \(v\).

sample

3
2 1 3
1 2
1 3

9