P10846 [EGOI 2024] Team Coding / 团队编程

Day 1 Problem C. 题面译自 [EGOI2024 teamcoding](https://wiki.egoi2024.nl/tasks/teamcoding/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。

埃因霍温巨型开源研究所（Eindhoven Gigantic Open-Source Institute，EGOI）公司有着非常严格的层级结构。除了 CEO Anneke，公司里的其他 $N - 1$ 名员工每人都有一个唯一的上司，并且层级结构中没有循环。你可以将公司的层级结构看作是以 Anneke 为根的树。由于这是一个多元化的公司，员工使用 $K$ 种不同的编程语言，但每位员工都有一种首选的编程语言。 Anneke 为公司团队准备了一个大型的新项目，她希望能投入尽可能多的资源。为了决定哪个团队来负责这个项目，她执行以下操作： 1. 选择一个人来领导团队。这也将确定项目使用的编程语言。每个在该团队领导下的子树中的员工且首选编程语言与团队领导相同的员工将参与这个项目。 2. 通过将首选编程语言与团队领导相同的员工调入她的团队来增加参与项目的员工数量。 为了最大化参与项目的员工数量，她可以多次执行以下调换操作： 1. 她选择两名员工： - 一名当前在团队领导的子树中且首选编程语言与团队领导不同的员工。 - 一名当前不在此子树中且首选编程语言与团队领导相同的员工。此外，这名员工需要与另一名被选中的员工处于相同的层级，即他们在向 Anneke 报告的链中有相同数量的上司。如果你将公司层级结构看作一棵树，那么这两名员工处于树的同一层级。 2. 这两名员工（且**仅**他们）交换公司层级结构中的位置。注意，报告给这两名员工的员工保持不变，只是更改了他们报告的对象。在下面的例子中，选择员工 $4$ 作为团队领导时，我们可以交换员工 $3$ 和 $2$，但不能交换员工 $1$ 和 $8$。  找出能够参与新项目的最大员工数量，以及实现这一目标所需的最少调换次数。

输入的第一行包含两个整数，$N$ 和 $K$，分别表示 EGOI 的员工数量和员工可能使用的编程语言的数量。 EGOI 的员工编号从 $0$ 到 $N - 1$，CEO Anneke 的编号为 $0$。下一行包含 $N$ 个整数 $l_i$，其中 $0 \le l_i < K$，表示员工的首选编程语言。 接下来的 $N - 1$ 行包含公司的结构。第 $i$ 行包含一个整数 $b_i$，其中 $0 \le b_i < N$，表示第 $i$ 号员工的直接上司。注意，$i$ 的取值范围是 $1$ 到 $N - 1$（包含两端），因为 CEO Anneke 没有上司。

输出一行包含两个整数，$P$ 和 $S$，表示通过任意次数的调换能够达到的最大参与项目的员工数量（包括团队领导）和实现这一目标所需的**最少**调换次数。

**样例解释** 在前两个样例中，公司结构如下所示，其中模式编码了编程语言（0 = “条纹”，1 = “点状”，2 = “纯色”）：  在样例 1 中，我们可以选择员工 $1$ 作为团队负责人，员工 $4$ 喜欢相同的编程语言，并且没有可能的交换来改善这一点。在样例 2 中，整个公司有 $3$ 名员工喜欢语言 $0$，这也是 Anneke 喜欢的语言，所以选择 Anneke 作为团队负责人会形成一个大小为 $3$ 的团队，不需要进行交换。  在样例 3 中，我们选择员工 $4$ 作为团队负责人，然后可以让员工 $1$ 和 $8$ 以及 $2$ 和 $3$ 交换团队，从而得到总共 $4$ 名员工喜欢与 $4$ 相同的语言，即语言 $2$（纯色）。在样例 4 中，选择员工 $6$ 作为团队负责人，并交换员工 $4$ 和 $7$ 以及 $1$ 和 $5$ 可以获得最大分数。注意，我们不能在选择团队负责人之前交换员工 $6$ 和 $3$ 以获得分数 $4$，因为我们必须首先确定团队负责人。 --- **数据范围** 对于全部数据，$1\le N\le 10^5$，$1\le K\le N$。 - 子任务一（$12$ 分）：第 $i$ 名员工的上司是 $i - 1$。 - 子任务二（$19$ 分）：$K\le 2$。 - 子任务三（$27$ 分）：对于每种编程语言，最多有 $10$ 名员工首选它。 - 子任务四（$23$ 分）：$N\le 2000$。 - 子任务五（$19$ 分）：无特殊限制。 注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。