链接: https://cses.fi/problemset/task/1688

板块: Tree Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一家公司拥有 $n$ 名员工，构成树形层级结构，其中除总经理外每位员工都有一位上司。

你需要处理 $q$ 次查询，形式为：员工 $a$ 和 $b$ 在层级中的最低公共上司是谁？

输入

第一行包含两个正整数 $n$ 和 $q$：员工数和查询数。员工编号为 $1,2,\dots,n$，且员工 $1$ 是总经理。

下一行有 $n-1$ 个整数 $e_2,e_3,\dots,e_n$：分别给出员工 $2,3,\dots,n$ 的上司。

最后有 $q$ 行描述查询。每行包含两个正整数 $a$ 和 $b$：员工 $a$ 和 $b$ 的最低公共上司是谁？

输出

输出每个查询的答案。

数据范围

$1 \le n,q \le 2 \cdot 10^5$ $1 \le e_i \le i-1$ $1 \le a,b \le n$

样例输入

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

样例输出

3
1
1