Problem D
Uzastopni
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.
Input
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$.
Output
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 |
---|---|
4 2 1 3 4 1 2 1 3 3 4 |
6 |
Sample Input 2 | Sample Output 2 |
---|---|
4 3 4 5 6 1 2 1 3 2 4 |
3 |
Sample Input 3 | Sample Output 3 |
---|---|
6 5 3 6 4 2 1 1 2 1 3 1 4 2 5 5 6 |
10 |