题目.txt

最近公共祖先(LCA)

最近公共祖先(LCA)
时间限制(普通/Java):2000MS/20000MS          运行内存限制:65536KByte
总提交:248            测试通过:75

描述


给定一棵有根树，询问数上某两个节点的公共祖先中离根最远的一个的编号

例如：

1

/    \ 

2       3

/  \     /  \

4   5   6   7

/  \

8          9

若询问节点4 和9 ，则回答2


输入


第一行一个数n 表示树的节点数

接下来n行每行一个数fi  第i+1行的数表示i节点的父节点编号

父节点编号为0的节点为根

第n+2行一个数m 表示问题数 

接下来m行 每行两个数xi yi 询问xi yi的公共祖先中离根最远的一个的编号

n+m<=100000


输出


M行

按输入顺序给出询问的回答

 


样例输入

9
0
1
1
2
2
3
3
5
5
1
4 9


样例输出

2

提示

Huge input, scanf is recommended

题目来源

Saint Pajamas