| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 13 | 6 | 5 | 41.667% |
The company Eindhoven Gigantic Open-Source Institute (EGOI) is structured in a very hierarchical way. Except for the CEO Anneke, each of the other $N-1$ employees in the company has a unique boss 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, the employees code in $K$ different 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 the following:
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.
The first line of the input contains two integers, $N$ and $K,ドル the number of employees of EGOI and the 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 $\ell_i$ with 0ドル\le \ell_i<K,ドル the preferred programming languages of the employees.
The next $N-1$ lines contain the company structure. The $i$th line contains an integer $b_i$ with 0ドル\le b_i<N,ドル the direct boss of the $i$th employee. Note that $i$ goes from 1ドル$ to $N,ドル as Anneke, the CEO, does not have a boss.
Output a single line with two integers, $P$ and $S,ドル the maximum number of employees (including the team lead) working on the new project you can reach with any number of switches and the minimum number of switches needed to reach this.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | The direct boss of employee $i$ is $i-1$ for all 1ドル\le i<N$. |
| 2 | 19 | $K\le 2$ |
| 3 | 27 | For each programming language, there are at most 10ドル$ employees that prefer it |
| 4 | 23 | $N\le 2,000円$ |
| 5 | 19 | No further constraints |
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
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 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 full company has 3ドル$ employees preferring language 0ドル$ which is also Anneke's preferred language, so choosing Anneke as the team lead gives a team of size 3ドル$ with no switches needed.
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ドル$ (yellow/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 fix the team lead first.