레이팅 미적용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:
- 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 \(4\) having been chosen as the team lead, we can swap employees \(3\) and \(2\) but not employees \(1\) and \(8\).
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.
(An illustrative figure from the official statement is omitted here.)
- \(1 \le N \le 10^5\).
- \(1 \le K \le N\).
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 \(1\) | \(12\) | The direct boss of employee \(i\) is \(i-1\) for all \(1\le i
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
The next \(N-1\) lines contain the company structure. The \(i\)th line contains an integer \(b_i\) with \(0\le b_i
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.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 12점 | None |
Subtask 2 | 19점 | None |
Subtask 3 | 27점 | None |
Subtask 4 | 23점 | None |
Subtask 5 | 19점 | None |
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