Petar is throwing a birthday party and he decided to invite some of the employees of his company where he is the CEO.

Each employee, including Petar, has a unique label from $1$ to $N$, and an accompanying type of jokes they tell $V_ i$. Also, each employee of the company except Petar has exactly one supervisor. Since Petar is the CEO of the company, he has the label $1$ and is directly or indirectly superordinate to all the employees.

At the birthday party, there are certain rules that all people present (including Petar) must follow.

  • At the party, there shouldn’t be two people that tell the same type of jokes.

  • Person $X$ cannot be invited if their direct supervisor is not invited.

  • Person $X$ cannot be invited if the set of jokes the invitees that person $X$ is superior to (directly or indirectly) tell and person $X$ don’t form a set of consecutive numbers.

The numbers in the set are consecutive if the difference between adjacent elements is exactly $1$ when the set is sorted ascendingly. For example, $(3, 1, 2)$ and $(5, 1, 2, 4, 3)$. Petar wants to know how many different sets of jokes he can see at his party with the listed constraints.


The first line of input contains the integer $N$, ($1 \leq N \leq 10\ 000$). The second line of input contains $N$ integers, the types of jokes person $i$ tells, $V_ i$, ($1 \leq V_ i \leq 100$). Each of the following $N-1$ lines contains two integers $A$ and $B$, ($1 \leq A, B \leq N$), denoting that person $A$ is directly superior to person $B$.


The first and only line of output must contain the number of different sets of jokes that comply to the previously listed constraints.

Sample Input 1 Sample Output 1
2 1 3 4
1 2
1 3
3 4
Sample Input 2 Sample Output 2
3 4 5 6
1 2
1 3
2 4
Sample Input 3 Sample Output 3
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6
CPU Time limit 3 seconds
Memory limit 1024 MB
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in