CF1062E Company

公司 $X$ 有 $n$ 名员工，编号从 $1$ 到 $n$。每个员工 $u$ 都有一个直属上司 $p_u$（$1 \le p_u \le n$），但员工 $1$ 没有上司。保证所有 $p_i$ 构成一棵树。若员工 $u$ 是员工 $v$ 的直属上司，或存在某个员工 $w$，使得 $w$ 负责 $v$，且 $u$ 是 $w$ 的直属上司，则称 $u$ 负责 $v$。此外，任何员工都被认为负责自己。 对于每个员工 $u$，定义其级别 $lv(u)$ 如下： - $lv(1)=0$ - $lv(u)=lv(p_u)+1$，其中 $u \neq 1$ 未来公司有 $q$ 个可能的运营方案。第 $i$ 个方案包含两个整数 $l_i$ 和 $r_i$，表示编号在区间 $[l_i, r_i]$ 内的所有员工（且仅这些员工）参与该方案。为了顺利执行方案，必须有一名项目经理，且该项目经理需要负责所有参与的员工。即，若选择员工 $u$ 作为第 $i$ 个方案的项目经理，则对于每个 $v \in [l_i, r_i]$，$u$ 必须负责 $v$。注意，$u$ 不一定在 $[l_i, r_i]$ 区间内。此外，$u$ 总是选择级别 $lv(u)$ 尽可能大的员工（级别越高，工资越低）。 在任何方案执行前，公司让 JATC 检查了他们的方案。JATC 一眼就发现，对于每个方案，都可以恰好减少一名参与员工而不影响方案的执行。公司出于节省成本的目的，询问 JATC 应该将哪位员工从方案中剔除，才能使所需项目经理的级别最大。JATC 已经知道答案，现在挑战你来解决这个问题。

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 100\,000$，$1 \le q \le 100\,000$），分别表示员工人数和方案数。 第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \le p_i \le n$），表示员工 $i$ 的直属上司为 $p_i$。 保证所有 $p_i$ 构成以 $1$ 为根的有向树。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i < r_i \le n$），表示第 $i$ 个方案涉及的员工编号区间。

输出 $q$ 行，每行包含两个整数，分别表示应从对应方案中剔除的员工编号，以及此时所需项目经理的最大可能级别。 如果有多种选择，输出任意一种均可。

例如：  在第一个询问中，可以选择剔除 $4$、$5$ 或 $6$，此时项目经理为 $3$。 在第二个询问中，若剔除除 $8$ 以外的任意员工，项目经理为 $1$。若剔除 $8$，项目经理为 $3$。由于 $lv(3)=1 > lv(1)=0$，所以选择剔除 $8$ 最优。 在第三个询问中，无论剔除哪位员工，项目经理都只能是 $1$。 在第四个询问中，若剔除 $9$ 或 $10$，项目经理为 $3$；若剔除 $11$，项目经理为 $7$。由于 $lv(7)=3>lv(3)=1$，所以选择剔除 $11$。 由 ChatGPT 4.1 翻译