## COCI '15 Contest 1 #6 Uzastopni

View as PDF

Points: 20 (partial)
Time limit: 0.3s
Memory limit: 32M

Problem types

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 to , and an accompanying type of jokes they tell . Also, each employee of the company except Petar has exactly one supervisor.

Since Petar is the CEO of the company, he has the label 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 cannot be invited if their direct supervisor is not invited.
• Person cannot be invited if the set of jokes the invitees that person is superior to (directly or indirectly) tell and person 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, and .

Petar wants to know how many different sets of jokes he can see at his party with the listed constraints.

#### Input Specification

The first line of input contains the integer , .

The second line of input contains integers, the types of jokes person tells, .

Each of the following lines contains two integers and , , denoting that person is directly superior to person .

In test cases worth 50% of total points, it will hold that does not exceed .

#### Output Specification

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

4
2 1 3 4
1 2
1 3
3 4

#### Sample Output 1

6

#### Explanation of Sample Output 1

It is possible to have the following sets of jokes at the party:

, , , , , .

#### Sample Input 2

4
3 4 5 6
1 2
1 3
2 4

#### Sample Output 2

3

#### Explanation for Sample Output 2

The only possible sets of jokes are: , , . Notice that the person telling joke cannot be at the party because, in that case, the set of jokes is not a set of consecutive numbers.

#### Sample Input 3

6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6

#### Sample Output 3

10