problem-5-7

Today is Akshat's Birthday and he has invited some of the employees of his company which he has recently started. Every employee has a unique label from 1 to N. Akshat being the CEO, has label 1.Moreover, every employee except Akshat has exactly one superior.All the guests including the CEO, has brought some jokes  J_i  to crack.

The party is organised keeping the following things in mind which each guest including Akshat must follow:
No two people should crack the same type of joke
An employee Y can be invited iff his direct supervisor is invited.
Employee Y cannot be invited if the set of jokes the 
invitees that person Y is superior to (directly 
or indirectly) tell and person Y don’t form a set of consecutive numbers

Akshat is curious to know how many different sets of jokes he can see at the party given the rules to keep in mind.

Input format
The first line contains an integer N , denoting the number of employees.

The following line contains N integers, the type of joke the ith employee brings with him  J_i 

Each of the next N-1 lines contain two integer X and Y, denoting that person X is direct senior of person Y

Output format
Output the different set of jokes that comply with the above constraints.

Constraints

 1 ≤ N ≤ 100 
 1 ≤ J_i ≤ 100 
 1 ≤ X, Y ≤ N 

*Note : There is no partial scoring for this problem *

SAMPLE INPUT
4 
2 1 3 4 
1 2 
1 3 
3 4

SAMPLE OUTPUT
6

Explanation

Following sets of jokes are allowed : {2},{2,3},{1,2},{1,2,3},{2,3,4},{1,2,3,4}

Source: hackerearth | Difficulty: HARD


Solutions: