Company Queries II

题目描述

一家公司有 n 名员工，他们构成一棵树状的层级结构，除总经理外每个员工都有一个上司。\n你的任务是处理 q 个查询，形式为：在层级结构中员工 a 和 b 的最近共同上司是谁？

输入格式

第一行输入包含两个整数 n 和 q：员工数量和查询数量。员工编号为 1,2,\dots,n，且员工 1 是总经理。\n下一行有 n-1 个整数 e_2,e_3,\dots,e_n：对于每个员工 2,3,\dots,n 给出他们的上司。\n最后有 q 行描述查询。每行包含两个整数 a 和 b：员工 a 和 b 的最近共同上司是谁？

输出格式

对每个查询输出答案。

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

3
1
1

提示

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

标签: CSES1688|树

来源

CSES1688|树