P14211 [ROI 2016 Day2] 快递服务

**译自 [ROI 2016](http://neerc.ifmo.ru/school/archive/2015-2016.html) Day2 T3.** ***[Курьерская служба](http://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-roi-2016-day2.pdf)***

在一家公司里有 $n$ 名员工，其中一人是董事。除了董事以外，每位员工都恰好有一位直属上级。 每位员工都有自己明确的工作职责。如果员工 $a$ 需要完成员工 $b$ 的工作，就必须向员工 $b$ 发送申请。根据公司制度，申请只能在员工与其直属上级之间直接传递：要么由员工传给直属上级，要么由上级传给直属下属。申请会在员工之间逐级传递，直到抵达员工 $b$。 为了减轻员工负担，公司雇佣了 $k$ 名快递员。第 $i$ 位快递员专门负责在员工 $a_i$ 与 $b_i$ 之间传递申请。当这两人中的一方需要将申请传递给另一方时，他会将申请交给快递员。快递员会按照公司制度依次传递申请，经过所有必要的中间员工，最终将其送达目标。在传递一份申请的过程中，快递员不会重复访问同一名员工。 为了优化开支，公司决定找到一对路径重合度最高的快递员，解雇其中一人，并将其工作交由另一人承担。我们定义快递员对的**重合度**为：这两名快递员路径中共同包含的“员工与其直属上级之间的双向通路”的数量。 请编写一个程序，找出重合度最大的两名快递员。

第一行包含两个整数 $n$ 和 $k$，分别表示员工人数与快递员人数（$2 \le n, k \le 2 \cdot 10^5$）。员工编号为 $1$ 到 $n$，董事编号为 $1$。 第二行包含 $n-1$ 个整数：$p_2, p_3, \ldots, p_n$，表示除董事外每位员工的直属上级编号（$1 \le p_i < i$）。 接下来 $k$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 位快递员负责的员工对（$1 \le a_i, b_i \le n$，且 $a_i \ne b_i$）。可能有多个快递员负责同一对员工。

第一行输出一个整数——两名快递员的最大重合度。 第二行输出两个不同的整数，范围为 $1$ 到 $k$，表示一对重合度最大的快递员编号。如果存在多组最优答案，输出任意一组即可。

### 样例解释 在第一个样例中，有两名快递员： - 第 1 名快递员负责在员工 1 与 3 之间传递申请。例如，从 1 传给 3 的过程中，申请先从 1 到 2，再从 2 到 3。 - 第 2 名快递员负责在员工 1 与 4 之间传递申请。例如，从 4 传给 1 的过程中，申请先从 4 到 2，再从 2 到 1。 两人路径的重合度为 1，因为他们都经过了员工 1（董事）与员工 2 之间的通路。 在第二个样例中，两名快递员的路径没有交集，因此重合度为 0。 在第三个样例中（见图示）： - 第一名快递员路径为员工 1 → 3； - 第二名快递员路径为员工 3 → 7； - 第三名快递员路径为员工 6 → 1。 :::align{center}  ::: 其中： - 第 1 与第 2 名快递员的路径重合在边 (2,3)； - 第 1 与第 3 名快递员的路径重合在边 (1,2)； - 第 2 与第 3 名快递员的路径重合在边 (2,4) 与 (4,5)。 因此，第 2 与第 3 名快递员的重合度最大，为 2。 在第四个样例中，所有快递员都传递申请于董事与员工 4 之间，因此任意一对快递员的重合度均为 3。可输出任意一对。 ### 数据范围 | 子任务编号 | 分值 | $n$ | $k$ | 附加限制 | 必须通过的子任务 | |:--:|:--:|:--:|:--:|:--:|:--:| | 1 | 29 | $2 \le n \le 100$ | $2 \le k \le 100$ | --- | | | 2 | 12 | $2 \le n \le 4000$ | $2 \le k \le 1000$ | --- | 1 | | 3 | 7 | $2 \le n \le 10^5$ | $2 \le k \le 1000$ | --- | 1–2 | | 4 | 8 | $2 \le n \le 10^5$ | $2 \le k \le 5000$ | --- | 1–3 | | 5 | 10 | $2 \le n \le 10^5$ | $2 \le k \le 50\,000$ | 任意员工到董事的路径长度不超过 20 | | | 6 | 12 | $2 \le n \le 10^5$ | $2 \le k \le 50\,000$ | 每位快递员都是重要快递员 | | | 7 | 12 | $2 \le n \le 10^5$ | $2 \le k \le 50\,000$ | --- | 1–6 | | 8 | 10 | $2 \le n \le 2 \cdot 10^5$ | $2 \le k \le 2 \cdot 10^5$ | --- | 1–7 | 翻译由 ChatGPT-5 完成