← 返回题目列表

AtCoder · pakencamp_2022_day1_g

G. 祖先查询

中文机器翻译题面 查看原题

配点 : 400 点

問題文

N 给出了一个有根的顶点树。在顶部 它们编号到 1 减去 N ,根是顶点。 您将收到 1 和顶点 i\,(2\leq i\leq N) 的父级是顶点 P_i 。

Q 个问题需要回答。 在第

i 题中,整数 给出了 X_i, Y_i 。顶点 它是 X_i 是顶点 是 Y_i 的祖先,计算两个顶点之间的距离。 d 按此顺序输出 d\geq2 是。边缘 X_i 和 按字典顺序比较 Y_i 的路径上的顶点数为 v_0,v_1,\ldots,v_d (但是,v_0=X_i, v_d=Y_i),v_1 输出。

制約

  • 3\leq N\leq 2\cdot 10^5
  • 1\leq P_i\leq i-1\, (2\leq i\leq N)
  • 1\leq Q\leq 2\cdot 10^5
  • 1\leq X_i,Y_i\leq N\, (1\leq i\leq Q)
  • 頂点 X_i 是顶点 是 Y_i 的祖先 打印第 (1\leq i\leq Q)
  • 頂点 X_i 与边缘 Y_i 的距离是 给出 2 以上

入力

输入是按以下格式从标准输入给出的。

N
P_2 P_3 \ldots P_N
Q
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q

出力

Q 行。 列出

i\, (1\leq i\leq Q) 行中,i 请输出对第几条质问的回答。


入力例 1

7
1 1 3 3 5 5
3
1 7
3 6
3 7

出力例 1

3
5
5

1 个查询中,(v_0,v_1,v_2,v_3)=(1,3,5,7) 和v_1=3 。

2 个查询中,(v_0,v_1,v_2)=(3,5,6) 和v_1=5 。

3 个查询中,(v_0,v_1,v_2)=(3,5,7) 和v_1=5 。


入力例 2

7
1 2 3 4 5 6
5
1 6
2 5
3 7
3 7
1 4

出力例 2

2
3
4
4
2

入力例 3

7
1 1 1 4 3 2
3
1 6
1 7
1 5

出力例 3

3
2
4