You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

​ 而树上节点的标号则是由这棵树的dfs序来决定的，即dfs序的第$i$个节点标号便是$i$。

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

输入格式

输入第一行共一个整数$n$，表示$T_0$的节点数。

接下来一行共$n-1$个整数，第$i$个整数$f_i$表示在$T_0$中，$i$号节点的父亲是$f_i$（节点编号为$0...n-1$），其中每个节点儿子从左到右的顺序恰好为儿子编号从小到大的顺序。

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

接下来$q$行，每行共两个整数$u_i,v_i$，表示询问$u_i,v_i$的最短距离。

输出格式

对于每个询问输出一个整数，表示$u_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% 的数据， $n\le10^5,k=0$ 。

对于 40% 的数据， $n\le10^5,k\le30$。

对于 100% 的数据， $n\le10^5,k\le10^9,1\le u_i,v_i\le10^9$

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