← 返回题目列表

AtCoder · awc0059_e

E. 最深的普通Boss

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

分数: 466 分

问题陈述

在高桥的公司中,员工的管理结构是通过树形结构形式的组织图来表示的。

员工编号为 1 to N。员工 1 是总裁,位于组织结构图的顶部(根)。

每位员工 i (2 \le i \le N) 仅有一名直接上级,其编号为 P_i.

该信息定义了一个有根树 N 顶点,以员工为根 1.

如果员工 可以从员工处联系 b 可以从员工那里联系到 a 跟随直接上级零次或多次,然后员工 b 被称为 优越 员工的 员工的 a.

特别是,每个员工也是自己的上级。此外,员工 1 是所有员工的上级。

在有根树中, 深度 顶点的 是从根到该顶点的路径上的边数。根深(员工 1) 是 0.

你被给予 Q 查询。

在 k第查询,员工编号 给出了 X_k 和 Y_k 。查找比这两名员工的上级员工的员工编号 X_k 和员工 Y_k 并且具有最大的深度。可以证明这样的员工确实存在。

请注意,如果员工 X_k 是员工的上级 Y_k,答案是 X_k,如果员工 Y_k 是员工的上级 X_k,答案是 Y_k (包括以下情况 X_k = Y_k).

约束

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq Q \leq 5 \times 10^4
  • 1 \leq P_i < i (2 \leq i \leq N)
  • 1 \leq X_k, Y_k \leq N (1 \leq k \leq Q)
  • 所有输入值均为整数

输入

N Q
P_2 P_3 \ldots P_N
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q
  • 第一行包含一个整数 N 代表员工人数和一个整数 Q 代表查询数量,以空格分隔。
  • 第二行包含 N-1 整数 P_2, P_3, \ldots, P_N 以空格分隔。 P_i 代表员工直属上级的员工编号 i.
  • 从第 3 行到 (Q+2)第行,给出每个查询。
  • 的 (2 + k)- 第行包含整数 X_k 和 Y_k 以空格分隔,代表 k第一个查询。

输出

打印 Q 行。

关于 k第行,打印答案 k-第一个查询作为整数。


示例输入 1

7 5
1 1 2 2 3 3
4 5
4 6
6 7
2 7
3 3

示例输出 1

2
1
3
1
3

示例输入 2

6 5
1 1 1 1 1
2 3
1 4
5 5
6 2
3 1

示例输出 2

1
1
5
1
1

示例输入 3

15 8
1 1 2 2 3 3 4 4 5 6 6 7 10 10
8 9
8 14
11 12
14 15
13 15
10 14
2 12
6 13

示例输出 3

4
2
6
10
1
10
1
3

示例输入 4

25 14
1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 9 10 10 11 13 14 16 18 21
20 12
20 25
22 23
24 19
17 23
14 15
21 6
18 24
1 25
11 12
5 6
8 16
17 18
2 25

示例输出 4

5
2
3
10
1
7
6
18
1
5
2
8
4
2

示例输入 5

2 4
1
1 1
1 2
2 2
2 1

示例输出 5

1
1
2
1