AT_pakencamp_2022_day1_g Ancestor Query

给定一棵有 $N$ 个节点的有根树，节点编号为 $1$ 到 $N$，根为节点 $1$。对于每个 $i\,(2\leq i\leq N)$，节点 $i$ 的父节点为 $P_i$。 有 $Q$ 个询问。对于每个第 $i$ 个询问，给定整数 $X_i, Y_i$，其中节点 $X_i$ 是节点 $Y_i$ 的祖先，且两节点间的距离 $d\geq2$。设连接 $X_i$ 和 $Y_i$ 的路径上的节点依次为 $v_0, v_1, \ldots, v_d$（其中 $v_0=X_i, v_d=Y_i$），请输出 $v_1$。

输入通过标准输入给出，格式如下： > $N$ $P_2$ $P_3$ … $P_N$ $Q$ $X_1$ $Y_1$ $X_2$ $Y_2$ … $X_Q$ $Y_Q$

输出共 $Q$ 行。 第 $i\,(1\leq i\leq Q)$ 行输出第 $i$ 个询问的答案。

### 样例解释 1 对于第 $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$。 ### 约束条件 - $3\leq N\leq 2\times 10^5$ - $1\leq P_i\leq i-1\, (2\leq i\leq N)$ - $1\leq Q\leq 2\times 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$。 由 ChatGPT 5 翻译