#4448. 树

题目描述

现在有一棵nn个点的树T0T_0,这是一个真正的树,因为每过一天它便会生长一次。 具体而言,每过一天,这棵树的叶子节点就会长出和T0T_0一模一样的子树,即第ii天的树TiT_i是将Ti1T_{i-1}的所有叶子替换成T0T_0而形成的。

​ 而树上节点的标号则是由这棵树的dfs序来决定的,即dfs序的第ii个节点标号便是iiimage

​ 现在这棵树已经生长了kk天,而你需要回答qq组询问,每次询问两个节点u,vu,v的最短距离。

输入格式

输入第一行共一个整数nn,表示T0T_0的节点数。

接下来一行共n1n-1个整数,第ii个整数fif_i表示在T0T_0中,ii号节点的父亲是fif_i(节点编号为0...n10...n-1),其中每个节点儿子从左到右的顺序恰好为儿子编号从小到大的顺序。

接下来一行共两个整数k,qk,q,意义如题面所示。

接下来qq行,每行共两个整数ui,viu_i,v_i,表示询问ui,viu_i,v_i的最短距离。

输出格式

对于每个询问输出一个整数,表示ui,viu_i,v_i的最短距离。

10
0 1 2 3 2 1 2 3 2
0 5
1 5
2 9
5 8
2 6
2 10
4
2
3
3
1
10
0 1 2 3 2 1 2 3 2
2 5
10 20
15 16
89 99
12 98
100 1
4
2
9
16
10

提示

对于 20% 的数据, n105,k=0n\le10^5,k=0

对于 40% 的数据, n105,k30n\le10^5,k\le30

对于 100% 的数据, n105,k109,1ui,vi109n\le10^5,k\le10^9,1\le u_i,v_i\le10^9

注意,当k=0k=0时,输入所给的节点之间的连边关系只表示树的形态,不代表最终点的编号。