5218. 公司查询（Company Queries II）
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 公司结构是一棵树：每个员工只有一个上级，除了总负责人（编号为$ 1$）。 给你 $q$ 个查询，每个查询给出两个员工$ a $和$ b$。 要求找出这两个人的 最近共同上级（lowest common boss）。 ## 输入格式 ## 输出格式 每行输出一个整数：表示 $a$ 和$ b$ 的最近公共老板。 ## 输入输出样例 ### 输入 #1 ``` n q e_2 e_3 \dots e_n a1 b1 a2 b2 \dots aq bq ``` ### 输出 #1 ``` 3 1 ``` ## 说明/提示 ### 数据规模与约定 - $1 \le n,q \le 2 \times 10^5$ - $1 \le e_i \le i-1$ - $1 \le a,b \le n$