Maximizing Team Participation with Hierarchical Swaps

Eindhoven Gigantic Open-Source Institute (EGOI) has a strict hierarchical structure. There are N employees numbered from 1 to N. Employee 1 is the CEO, Anneke. For every other employee (from 2 to N), a unique direct supervisor is given, forming a rooted tree with Anneke as the root. In addition, the company uses K different programming languages, and every employee has a favorite language.

Anneke is preparing a large new project and wants to involve as many employees as possible. To choose the team that will work on the project she performs the following steps:

1. Choose one employee as the team leader. This choice also fixes the project language as the favorite language of the team leader. Initially, all employees in the subtree of the team leader (including the leader) whose favorite language equals that of the leader will participate in the project.
2. Then, in order to maximize participation, Anneke can perform a sequence of swap operations. In each swap operation, she selects two employees under the following conditions:
   1. One employee in the team leader’s subtree whose favorite language differs from the team leader’s language.
   2. One employee outside the team leader’s subtree whose favorite language is the same as the team leader’s language. In addition, these two employees must be on the same level of the company hierarchy (i.e. the length of the reporting chain from Anneke is equal for both).
   When these two employees swap positions in the company hierarchy (their own reporting relationships are exchanged, while those of their subordinates remain unchanged), the employee coming from outside joins the team (because he/she now lies in the subtree of the team leader) while the other leaves.

If we denote by \( L \) the favorite language of the team leader, then for any level \( d \) in the tree which appears in the team leader’s subtree, let

[ \text{inside}{d} = \text{number of employees at level } d \text{ in the team leader's subtree}, \quad \text{correct}{d} = \text{number of those with favorite } L. ]

Also, let

[ \text{global}_{d}(L) = \text{total number of employees at level } d \text{ in the whole company with favorite } L. ]

For each level \( d \) in the team leader’s subtree, one may swap at most \( \min(\text{inside}_{d}-\text{correct}_{d}, \; \text{global}_{d}(L)-\text{correct}_{d}) \) employees. Thus, the final number of participating employees if the team leader is chosen as u (with favorite language \( L \)) is given by:

[ \text{team}(u) = \sum_{d \in D(u)} \Bigl( \text{correct}{d} + \min\bigl(\text{inside}{d}-\text{correct}{d}, ; \text{global}{d}(L)-\text{correct}_{d}\bigr) \Bigr), ]

where \( D(u) \) denotes the set of levels present in the subtree of u. The total number of swaps needed is the sum over levels of the minimums above. Your task is to choose a team leader and perform swaps (if any) so that the final number of participating employees is maximized. If there are multiple ways to achieve the maximum participation, you must choose the one with the minimum number of swaps.

Input Format

The first line contains two integers N and K (1 ≤ N ≤ 2000, 1 ≤ K ≤ K_max), the number of employees and the number of programming languages respectively.

The second line contains N integers. The i-th integer is the favorite programming language of employee i (an integer between 1 and K). Employee 1 is the CEO, Anneke.

Then follow N - 1 lines. For i from 2 to N, the (i-1)-th line contains one integer indicating the supervisor of employee i (a number less than i).

Output Format

Output two integers separated by a space: the maximum number of employees that can participate in the project and the minimum number of swaps needed to achieve that.

---

Note: In all formulas, use LaTeX format. The swap operations are allowed to be performed in any order and any number of times.

inputFormat

The input begins with a line containing two integers N and K.

The next line contains N integers representing the favorite programming language of each employee from 1 to N.

Each of the following N - 1 lines contains one integer — the supervisor of employee 2, 3, ..., N respectively.

outputFormat

Output two space‐separated integers: the maximum number of participating employees and the minimum number of swaps needed.

sample

3 2
1 2 1
1
1

2 0