CF2223C Zhily and Signpost

在返回基地的路上，Jily 迷路了。他发现前方的道路构成了一棵树。在每一个岔路口都有一个路标，但这些路标受到了异常磁场的影响，不断旋转。Zhily 很担心 Jily，想请你帮忙解答几个问题。每次，对于给定的某一时刻，他会问你：如果 Jily 从起点出发，最终会停在树上的哪个节点。 给定一棵有 $n$ 个节点的树，根节点为 $1$。节点 $u$ 有 $d_u$ 个子节点，且这些子节点按节点编号递增排序，分别为 $s_{u,0},\ldots,s_{u,d_u-1}$。通过每条边需要一定时间，具体地，节点 $u$ 与其父节点之间的边需要 $l_u$ 时间穿过。 树上每个非叶节点都有一个路标，路标指向其某一个子节点。当你处于此类节点时，必须立即沿着路标指向的子节点向下走，直至到达叶节点，并立即停下。 路标会随时间变动。于时刻 $m$，节点 $u$ 的路标会指向其第 $((m\bmod d_u)+1)$ 个子节点，即节点 $s_{u,m \bmod d_u}$。 现在有 $q$ 次询问。每次询问会给定一个时刻 $m$，你需要判断从根节点出发，按照上述规则最终会停在哪个叶节点。

每组测试数据包含多组测试用例。第一行为测试用例组数 $t$（$1 \le t \le 10^4$）。接下来依次给出每组测试用例： 每个测试用例的第一行为两个正整数 $n, q$（$1 \le n \le 5 \cdot 10^5,\, 1 \le q \le 10^6$）。 第二行为 $n-1$ 个正整数 $f_2,\ldots,f_n$（$1 \le f_u < u$），表示节点 $u$ 的父节点编号为 $f_u$。 第三行为 $n-1$ 个非负整数 $l_2,\ldots,l_n$（$0 \le l_u \le 10^9$），表示节点 $u$ 和其父节点之间的边所需时间为 $l_u$。 第四行为 $q$ 个非负整数 $m_1,\ldots,m_{q}$（$0 \le m_i \le 10^{18}$），分别表示 $q$ 次询问的时刻。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$，所有测试用例中 $q$ 的总和不超过 $10^6$。

对于每个测试用例，输出一行，包含 $q$ 个正整数，依次表示每个询问的答案。

第一组测试用例如下图所示。  如果你在时刻 $4$ 出发，那么此时节点 $1$ 的路标指向节点 $2$，你将在时刻 $14$ 到达节点 $2$ 并停下。 第二组测试用例如下图所示。  如果你在时刻 $3$ 出发，那么此时节点 $1$ 的路标指向节点 $2$，你将在时刻 $4$ 到达节点 $2$。此时节点 $2$ 的路标指向节点 $4$，你将在时刻 $7$ 到达节点 $4$。此时节点 $4$ 的路标指向节点 $9$，你将在时刻 $15$ 到达节点 $9$ 并停下。 由 ChatGPT 5 翻译