← 返回题目列表

Codeforces · 1062/E

E. 公司

中文机器翻译题面 查看原题

公司 $$$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$$$ for $$$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 已经找到了答案,并要求您也这样做。

输入

第一行包含两个整数 $$$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$$$) 表示 $$$p_i$$$ 是员工 $$$i$$$ 的直接老板。

保证值 $$$p_i$$$ 形成根为 $$$1$$$ 的有向树。

以下 $$$q$$$ 行均包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i<r_i \le n$$$) — 相应计划中涉及的员工范围。

输出

打印 $$$q$$$ 行,每行包含两个整数 - 应从相应计划中踢出的员工人数以及在这种情况下项目经理的最高可能级别。

如果有多种选择该员工的方法,请打印其中任何一种。

示例

输入 #1

11 5
1 1 3 3 3 4 2 7 7 6
4 6
4 8
1 11
9 11
8 11

输出 #1

4 1
8 1
1 0
11 3
8 1

注意

在示例中:

在第二个查询中,如果我们选择员工 $$$8$$$ 以外的任何员工,则项目经理将为 $$$1$$$。如果我们选择$$$8$$$,项目经理将为$$$3$$$。由于 $$$lv(3)=1 > lv(1)=0$$$,因此选择 $$$8$$$ 是最佳策略。

在第三个查询中,无论我们如何选择员工,项目经理始终是$$$1$$$。

在第四个查询中,如果我们选择 $$$9$$$ 或 $$$10$$$ 那么项目经理将为 $$$3$$$。如果我们选择$$$11$$$,那么项目经理将为$$$7$$$。由于 $$$lv(7)=3>lv(3)=1$$$,我们选择 $$$11$$$ 作为答案。