Background

Day 1 Problem C.

The statement is translated from EGOI2024 teamcoding. The translation comes from ChatGPT and has been proofread manually. If there are any mistakes, please contact rui_er.

Problem Description

The Eindhoven Gigantic Open-Source Institute (EGOI) company has a very strict hierarchy. Besides the CEO Anneke, each of the other $N - 1$ employees has exactly one direct boss, and there are no cycles in the hierarchy. You can view the company hierarchy as a tree rooted at Anneke. Since this is a diverse company, employees use $K$ different programming languages, but each employee has one preferred programming language.

Anneke has prepared a large new project for the company, and she wants to invest as many resources as possible. To decide which team will take charge of this project, she does the following:

1. Choose one person to lead the team. This also determines the programming language used for the project. Every employee in the subtree under the team leader whose preferred programming language is the same as the team leader’s will participate in the project.

2. Increase the number of employees participating in the project by moving employees whose preferred programming language is the same as the team leader’s into her team.

   To maximize the number of participating employees, she may perform the following swap operation multiple times:

   1. She chooses two employees:
      • One employee who is currently in the team leader’s subtree and whose preferred programming language is different from the team leader’s.
      • One employee who is currently not in this subtree and whose preferred programming language is the same as the team leader’s. In addition, this employee must be at the same level as the other chosen employee, meaning they have the same number of bosses on the chain reporting up to Anneke. If you view the company hierarchy as a tree, then these two employees are on the same depth.
   2. These two employees (and only them) swap their positions in the company hierarchy. Note that the employees who report to these two employees stay the same; only who they report to is changed. In the example below, when choosing employee $4$ as the team leader, we can swap employees $3$ and $2$, but we cannot swap employees $1$ and $8$.

Find the maximum number of employees that can participate in the new project, and the minimum number of swaps needed to achieve it.

Input Format

The first line contains two integers, $N$ and $K$, representing the number of employees in EGOI and the number of programming languages that employees may use.

EGOI employees are numbered from $0$ to $N - 1$, and CEO Anneke has number $0$. The next line contains $N$ integers $l_i$, where $0 \le l_i < K$, indicating the preferred programming language of employee $i$.

The next $N - 1$ lines describe the company structure. Line $i$ contains an integer $b_i$, where $0 \le b_i < N$, indicating the direct boss of employee $i$. Note that $i$ ranges from $1$ to $N - 1$ (inclusive), because CEO Anneke has no boss.

Output Format

Output one line containing two integers, $P$ and $S$, representing the maximum number of employees that can participate in the project (including the team leader) after any number of swaps, and the minimum number of swaps needed to achieve this maximum.

5 3
0 1 2 2 1
0
1
2
3

2 0

4 2
0 1 0 0
0
0
1

3 0

9 3
0 0 2 1 2 0 2 1 2
4
8
1
0
4
1
0
7

4 2

8 3
0 2 1 2 2 1 1 1
6
3
0
6
3
0
3

3 2

Hint

Sample Explanation

In the first two samples, the company structure is as shown below, where the patterns encode the programming languages (0 = “striped”, 1 = “dotted”, 2 = “solid”):

In sample 1, we can choose employee $1$ as the team leader. Employee $4$ likes the same programming language, and there is no possible swap to improve this. In sample 2, the whole company has $3$ employees who like language $0$, which is also the language Anneke likes, so choosing Anneke as the team leader forms a team of size $3$ and requires no swaps.

In sample 3, we choose employee $4$ as the team leader, and then we can swap the teams of employees $1$ and $8$ and of employees $2$ and $3$, obtaining a total of $4$ employees who like the same language as $4$, namely language $2$ (“solid”). In sample 4, choosing employee $6$ as the team leader and swapping employees $4$ and $7$ as well as employees $1$ and $5$ achieves the maximum score. Note that we cannot swap employees $6$ and $3$ before choosing the team leader to get score $4$, because we must determine the team leader first.

Constraints

For all testdata, $1\le N\le 10^5$, $1\le K\le N$.

• Subtask 1 ($12$ points): Employee $i$’s boss is $i - 1$.
• Subtask 2 ($19$ points): $K\le 2$.
• Subtask 3 ($27$ points): For each programming language, at most $10$ employees prefer it.
• Subtask 4 ($23$ points): $N\le 2000$.
• Subtask 5 ($19$ points): No additional constraints.

Note: Some test points are placed into multiple subtasks in EGOI. To save judging resources and the workload of organizing the data, these test points are placed in the subtask with the smallest index among all subtasks that contain them. This may cause a solution to get a higher score than expected, but still not pass the problem.

Translated by ChatGPT 5