Problem N
Team Coding
The company Eindhoven Gigantic Open-Source Institute (EGOI)
is structured in a very hierarchical way. Except for the CEO
Anneke, each of the other
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 the following:
-
Pick a person to lead the team. This will also define the programming language the project is coded in. Every employee who is in the subtree below the team lead and prefers the same programming language will work on the problem.
-
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 the following switching operation any number of times:
-
She picks two employees:
-
One employee who is currently in the subtree of the team lead and does not prefer 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 to be on the same level as the other chosen employee; that is, they need to have the same number of higher-ups in the report chain to Anneke. If you imagine the company hierarchy as a tree, then the two employees are on the same level of the tree.
-
-
Those two employees (and only them – not any other employees) switch positions in the company hierarchy. Note that employees reporting to the two affected employees stay in place and just change whom they report to. In the example below, with employee
having been chosen as the team lead, we can swap employees and but not employees and .
-
Find the maximum number of employees working on the new project you can reach and the minimum number of switching operations needed to achieve this.
Input
The first line of the input contains two integers,
The employees of EGOI are numbered from
The next
Output
Output a single line with two integers,
Constraints and Scoring
-
. -
.
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 |
Limits |
|
|
The direct boss of employee |
|
|
|
|
|
For each programming language, there are at most
|
|
|
|
|
|
No further constraints |
Examples
In the first two samples, the company structure looks as follows, where the pattern encodes the programming language (0 = “striped”, 1 = “dotted”, 2 = “plain”):
In sample 1, we can choose employee
In sample 3, we choose employee
Sample Input 1 | Sample Output 1 |
---|---|
5 3 0 1 2 2 1 0 1 2 3 |
2 0 |
Sample Input 2 | Sample Output 2 |
---|---|
4 2 0 1 0 0 0 0 1 |
3 0 |
Sample Input 3 | Sample Output 3 |
---|---|
9 3 0 0 2 1 2 0 2 1 2 4 8 1 0 4 1 0 7 |
4 2 |
Sample Input 4 | Sample Output 4 |
---|---|
8 3 0 2 1 2 2 1 1 1 6 3 0 6 3 0 3 |
3 2 |