teamcoding
Day1 Tasks

European Girls'
Olympiad in Informatics
21 – 27 July 2024
The Netherlands

English (ISC)

C. Team Coding
Problem NameTeam Coding

Time Limit

4 seconds

Memory Limit

1 gigabyte

The company Eindhoven Gigantic Open-Source Institute (EGOI) is structured in a very hierarchicalway. Except for the CEO Anneke, each of the other N − 1 employees in the company has a uniqueboss that they report to, and there are no cycles in the hierarchy. You can think of the company
hierarchy as a tree rooted in the vertex corresponding to Anneke. As this is a diverse company, theemployees code in K diﬀerent programming languages, but every employee has exactly one
preferred programming language.
Anneke has a big new project for a team in her company to work on. She wants to put as many
resources as possible into this project. To decide the team who will work on this, she does thefollowing:
1. Pick a person to lead the team. This will also deﬁne the programming language the project iscoded in. Every employee who is in the subtree below the team lead and prefers the same
programming language will work on the problem.
2. Increase the number of employees who work on the project, by switching employees who
prefer the same programming language as the team lead into her team.
To maximize the number of employees who work on the project, she can perform thefollowing switching operation any number of times:
1. She picks two employees:
One employee who is currently in the subtree of the team lead and does notprefer the same programming language as the team lead.
One employee who is not in this subtree at the moment and prefers the same
programming language as the team lead. Additionally, this employee needs tobe on the same level as the other chosen employee; that is, they need to havethe same number of higher-ups in the report chain to Anneke. If you imagine

teamcoding (1 of 5)the company hierarchy as a tree, then the two employees are on the same levelof the tree.
2. Those two employees (and only them – not any other employees) switch positions in
the company hierarchy. Note that employees reporting to the two aﬀected employees
stay in place and just change whom they report to. In the example below, withemployee 4 having been chosen as the team lead, we can swap employees 3 and 2 but
not employees 1 and 8.

Find the maximum number of employees working on the new project you can reach and theminimum number of switching operations needed to achieve this.

Input
The ﬁrst line of the input contains two integers, N and K , the number of employees of EGOI andthe number of programming languages the employees might use.
The employees of EGOI are numbered from 0 to N − 1, and Anneke the CEO has number 0. The
next line contains N integers ℓi with 0 ≤ ℓi < K , the preferred programming languages of theemployees.
The next N − 1 lines contain the company structure. The i th line contains an integer bi with0 ≤ bi < N , the direct boss of the ith employee. Note that i goes from 1 to N − 1 (inclusive), as
Anneke, the CEO, does not have a boss.

OutputOutput a single line with two integers, P and S , the maximum number of employees (includingthe team lead) working on the new project you can reach with any number of switches and theminimum number of switches needed to reach this.

Constraints and Scoring

teamcoding (2 of 5)1 ≤ N ≤ 105 .
1 ≤ K ≤ N.
Your solution will be tested on a set of test groups, each worth a number of points. Each test
group contains a set of test cases. To get the points for a test group, you need to solve all test
cases in the test group.
Group

Score

Limits112The direct boss of employee i is i − 1 for all 1 ≤ i < N .

219K ≤2327423N ≤ 2 000519No further constraints

For each programming language, there are at most 10 employees that preferitExamples
In the ﬁrst two samples, the company structure looks as follows, where the pattern encodes theprogramming language (0 = “striped”, 1 = “dotted”, 2 = “plain”):

In sample 1, we can choose employee 1 as the team lead with employee 4 preferring the same
programming language and there are no possible switches to improve this. In sample 2, the fullcompany has 3 employees preferring language 0 which is also Anneke's preferred language, sochoosing Anneke as the team lead gives a team of size 3 with no switches needed.

teamcoding (3 of 5)

In sample 3, we choose employee 4 as the team lead and then we can have employees 1 & 8 and 2& 3 switch teams to get a total of 4 employees preferring the same language as 4, namely
language 2 (plain). In sample 4, the maximum score can be obtained by choosing employee 6 as
the team lead and switching employees 4 & 7 and 1 & 5. Note that we cannot switch employees 6& 3 before choosing the team lead to get a score of 4 because we have to ﬁx the team lead ﬁrst.

teamcoding (4 of 5)

Input5 30 1 2 2 1

Output2 001234 2

3 0

0 1 0 00019 3

4 20 0 2 1 2 0 2 1 24810
41078 3

3 20 2 1 2 2 1 1 1630630
3

teamcoding (5 of 5)