Problem Background

Day 1 Problem C.

The problem statement is translated from EGOI2024 teamcoding. The translation was done using ChatGPT and manually proofread. If there are any errors, please contact rui_er.

Problem Description

The Eindhoven Gigantic Open-Source Institute (EGOI) has a very strict hierarchical structure. Apart from CEO Anneke, the other $N - 1$ employees each have a unique supervisor, and there are no cycles in the hierarchy. You can think of the company's hierarchy as a tree with Anneke as the root. Since it is a diverse company, employees use $K$ different programming languages, but each employee has a preferred programming language.

Anneke has prepared a large new project for the company team and wants to allocate as many resources as possible. To decide which team will be in charge of the project, she performs the following operations:

1. Select a person to lead the team. This will also determine the programming language used for the project. Each employee in the subtree under the team leader who has the same preferred programming language as the team leader will participate in the project.

2. Increase the number of employees participating in the project by moving employees whose preferred programming language matches that of the team leader into her team.

   To maximize the number of employees participating in the project, she can perform the following swap operations multiple times:
   1. She selects two employees:
   - One who is currently in the subtree of the team leader and whose preferred programming language is different from that of the team leader.
   - One who is currently not in this subtree and whose preferred programming language matches that of the team leader. Additionally, this employee must be at the same level as the other selected employee, meaning they have the same number of supervisors in the chain reporting to Anneke. If you think of the company hierarchy as a tree, these two employees are at the same level.
   2. These two employees (and only they) swap their positions in the company hierarchy. Note that the employees reporting to these two remain unchanged, only the person they report to is changed. In the example below, when selecting employee $4$ as the team leader, we can swap employees $3$ and $2$, but not employees $1$ and $8$.

Determine the maximum number of employees that can participate in the new project and the minimum number of swaps required to achieve this.

Input Format

The first line of input contains two integers, $N$ and $K$, representing the number of employees at EGOI and the number of possible programming languages used by the employees, respectively.

The employees are numbered from $0$ to $N - 1$, with CEO Anneke numbered as $0$. The next line contains $N$ integers $l_i$, where $0 \le l_i < K$, representing the preferred programming language of each employee.

The following $N - 1$ lines describe the structure of the company. The $i$-th line contains an integer $b_i$, where $0 \le b_i < N$, representing the direct supervisor of the $i$-th employee. Note that $i$ ranges from $1$ to $N - 1$ (inclusive), as CEO Anneke has no supervisor.

Output Format

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

Sample Input and Output

Sample Input #1

5 3
0 1 2 2 1
0
1
2
3

Sample Output #1

2 0

Sample Input #2

4 2
0 1 0 0
0
0
1

Sample Output #2

3 0

Sample Input #3

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

Sample Output #3

4 2

Sample Input #4

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

Sample Output #4

3 2

Notes

Sample Explanation

In the first two samples, the company structure is shown below, with the pattern encoding 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 are no possible swaps to improve this. In Sample 2, the entire company has $3$ employees who like language $0$, which is also the language Anneke likes, so choosing Anneke as the team leader will form a team of size $3$ without needing any swaps.

In Sample 3, we choose employee $4$ as the team leader, then we can swap employees $1$ and $8$ as well as $2$ and $3$, resulting in a total of $4$ employees liking the same language as $4$, which is language $2$ (solid). In Sample 4, choosing employee $6$ as the team leader and swapping employees $4$ and $7$ as well as $1$ and $5$ can achieve the maximum score. Note that we cannot swap employees $6$ and $3$ before choosing the team leader to get a score of $4$, as we must first determine the team leader.

Data Range

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

• Subtask 1 (12 points): The supervisor of the $i$-th employee 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 special restrictions.

Note: Some test cases are included in multiple subtasks at EGOI. To save evaluation resources and reduce data collation workload, these test cases are placed in the subtask with the smallest number that includes them. This may result in a code receiving a higher score than expected, but it will not allow passing the problem.

见题面 Input 部分

见题面 Output 部分