COCI '15 Contest 1 #6 Uzastopni

View as PDF

Submit solution

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 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 Specification

The first line of input contains the integer N, (1 \le N \le 10\,000).

The second line of input contains N integers, the types of jokes person i tells, V_i (1 \le V_i \le 100).

Each of the following N-1 lines contains two integers A and B, (1 \le A, B \le N), denoting that person A is directly superior to person B.

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

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:

\{2\}, \{2, 3\}, \{2, 3, 4\}, \{1, 2, 3, 4\}, \{1, 2\}, \{1, 2, 3\}.

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: \{3\}, \{3, 4\}, \{3, 4, 5\}. Notice that the person telling joke 6 cannot be at the party because, in that case, the set of jokes \{4, 6\} 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

Comments

There are no comments at the moment.