P13625 [ICPC 2024 APC] Tree Quiz

你的朋友想考考你。给你一棵有 $n$ 个节点的有根树，节点编号从 $1$ 到 $n$。对于每个节点 $i$，它的父节点是 $p_i$，除了根节点（没有父节点的节点）的 $p_i=0$。如果节点 $u=v$，或者节点 $u$ 是节点 $v$ 的父节点（如果存在）的祖先，那么我们说节点 $u$ 是节点 $v$ 的一个祖先。 如果节点 $z$ 同时是节点 $x$ 和节点 $y$ 的祖先，我们称节点 $z$ 是节点 $x$ 和 $y$ 的一个共同祖先。如果节点 $z$ 是节点 $x$ 和 $y$ 的一个共同祖先，并且节点 $x$ 和 $y$ 的任何一个共同祖先也都是节点 $z$ 的祖先，那么我们称节点 $z$ 是节点 $x$ 和 $y$ 的最近共同祖先。我们将节点 $x$ 和 $y$ 的最近共同祖先表示为 $\operatorname{LCA}(x,y)$。特别地，$\operatorname{LCA}(x,x)=x$。 你的朋友想要运行以下伪代码： ``` let L be an empty array for x = 1 to n for y = 1 to n append ((x-1)*n*n + (LCA(x,y)-1)*n + (y-1)) to L sort L in non-decreasing order ``` 你的朋友有 $q$ 个问题，编号从 $1$ 到 $q$。在第 $j$ 个问题中，会给你一个整数 $k_j$，并要求你找出数组 $L$ 中的第 $k_j$ 个元素。请注意，$L$ 是以 $1$ 为起始下标的，所以其下标范围从 $1$ 到 $n^2$。为了通过测试，你必须回答所有问题。

输入的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 100,000$；$1 \le q \le 100,000$）。第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（对于所有的 $i$，$0 \le p_i \le n$）。保证给定的值代表一棵有根树。接下来的 $q$ 行每行包含一个整数。第 $j$ 行包含 $k_j$（$1 \le k_j \le n^2$）。

对于每个问题，按顺序输出一个整数作为问题的答案。

输入中的树如图 K.1 所示。  $L$ 的元素为 $(0, 6, 8, 12, 14, 30, 31, 32, 33, 34, 56, 58, 60, 62, 64, 80, 81, 82, 84, 93, 106, 108, 110, 112, 124)$。