7624: [CSES Problem Set] Company Queries II
[Creator : ]
Description
A company has $n$ employees, who form a tree hierarchy where each employee has a boss, except for the general director.
Your task is to process $q$ queries of the form: who is the lowest common boss of employees $a$ and $b$ in the hierarchy?
Your task is to process $q$ queries of the form: who is the lowest common boss of employees $a$ and $b$ in the hierarchy?
Input
The first input line has two integers $n$ and $q$: the number of employees and queries. The employees are numbered $1,2,\dots,n$, and employee $1$ is the general director.
The next line has $n-1$ integers $e_2,e_3,\dots,e_n$: for each employee $2,3,\dots,n$ their boss.
Finally, there are $q$ lines describing the queries. Each line has two integers $x$ and $k$: who is employee $x$'s boss $k$ levels higher up?
The next line has $n-1$ integers $e_2,e_3,\dots,e_n$: for each employee $2,3,\dots,n$ their boss.
Finally, there are $q$ lines describing the queries. Each line has two integers $x$ and $k$: who is employee $x$'s boss $k$ levels higher up?
Output
Print the answer for each query.
Constraints
$1≤n,q≤2⋅10^5$
$1 \le e_i \le i-1$
$1 \le x \le n$
$1 \le k \le n$
$1 \le e_i \le i-1$
$1 \le x \le n$
$1 \le k \le n$
Sample 1 Input
5 3
1 1 3 3
4 5
2 5
1 4
Sample 1 Output
3
1
1