分数: 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