题目描述

本题与 E 题使用相同的定义。但本题并不要求与 E 题相同的答案。

有一棵包含 $n+1$ 个顶点的二叉树（$n$ 为奇数），顶点编号为 $0,1,\ldots,n$。每个顶点上最多可以写一个字母，一开始所有顶点上都没有写字母。树的根节点是顶点 $0$。

在树中，顶点 $0$ 是顶点 $1$ 的父节点，其余顶点要么有 $2$ 个子节点，要么没有子节点。

Bob 迷失在树的某个顶点，他希望通过到达顶点 $0$ 的方式逃出树。对于大多数有常识的人来说，这很容易。但由于 Bob 很笨，他发明了一种全新的遍历树的方法，被称为“笨蛋优先遍历法”（"Idiot First Search"）。

当 Bob 处于顶点 $v$ 时（$1 \le v \le n$），他按照如下规则移动：

• 如果顶点 $v$ 是叶节点，Bob 总是移动到 $v$ 的父节点；否则，继续判断以下情况。
• 如果顶点 $v$ 上什么都没写，Bob 在顶点 $v$ 上写下 'L'，并移动到 $v$ 的左儿子；
• 如果顶点 $v$ 上写有字母 'L'，Bob 将其覆盖为 'R'，并移动到 $v$ 的右儿子；
• 如果顶点 $v$ 上写有字母 'R'，Bob 擦除它，移动到 $v$ 的父节点。

Bob 移动到相邻顶点每次正好需要 $1$ 秒，因此进行 $x$ 次移动总共需要 $x$ 秒。

已经证明，无论 Bob 从哪一个顶点出发，都能在有限（尽管可能非常大）的时间内到达顶点 $0$。我们不知道是谁证明了这点，肯定不是 Bob，但这一点确实被证明了。

你需要回答 $q$ 个如下类型的询问：

• $v\;k$：假设 Bob 从顶点 $v$ 出发，恰好经过 $k$ 次移动后，Bob 处于哪个顶点（$1 \le v \le n$）。

对于每个询问，设 $T_v$ 表示 Bob 从顶点 $v$ 到达顶点 $0$ 的所需时间。保证每个询问 $k < T_v$。

输入格式

每个测试点包含多组测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是每组测试用例的数据。

每个测试用例的第一行包含整数 $n$ 和 $q$（$1 \le n \le 300\,001$，$1 \le q \le 400\,000$，$n$ 为奇数）。

接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$，分别为顶点 $i$ 的左右子节点编号（$0 \le l_i,r_i \le n$）。

对于每个顶点，如果 $l_i = r_i = 0$，则表示该顶点没有子节点。否则，$l_i$ 和 $r_i$ 分别为顶点 $i$ 的左儿子和右儿子。

接下来的 $q$ 行，每行包含两个整数 $v_j$ 和 $k_j$，表示第 $j$ 个询问（$1 \le v_j \le n$，$0 \le k_j < \min(10^9+7, T_{v_j})$）。

保证输入描述的是一棵合法的二叉树，满足题目中所述的条件。

且所有测试用例中的 $n$ 之和不超过 $300\,001$。

所有测试用例中的 $q$ 之和不超过 $400\,000$。

输出格式

对于每个测试用例，按询问顺序依次输出每个询问的答案，每个测试用例输出一行。

样例

3
1 1
0 0
1 0
5 5
2 3
0 0
4 5
0 0
0 0
3 6
3 8
3 11
4 7
5 8
7 7
2 3
4 5
0 0
6 7
0 0
0 0
0 0
1 9
2 18
3 11
3 12
3 13
5 7
7 17

1
2 3 5 2 1
2 2 1 3 1 2 4

样例说明

在第一个测试用例中，只有两个顶点，顶点 $0$ 和顶点 $1$。很显然，Bob 从顶点 $1$ 出发经过 $0$ 次移动后仍在顶点 $1$。

在第二个测试用例中，树结构如下：

Bob 从顶点 $3$ 出发到达顶点 $0$ 需要 $14$ 秒。具体移动过程如下：

$$3 \xrightarrow{\mathtt{L}} 4 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{R}} 5 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{L}} \color{red}{2} \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{R}} \color{red}{3} \xrightarrow{\mathtt{L}} 4 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{R}} \color{red}{5} \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{X}} 0$$

其中，箭头上方的字母表示移动前顶点上的字母，$\mathtt{X}$ 表示该顶点上没有写字母。

如红色标出：

• Bob 从顶点 $3$ 出发，进行 $6$ 次移动后，Bob 在顶点 $2$；
• Bob 从顶点 $3$ 出发，进行 $8$ 次移动后，Bob 在顶点 $3$；
• Bob 从顶点 $3$ 出发，进行 $11$ 次移动后，Bob 在顶点 $5$。

由 ChatGPT 5 翻译

来源

Codeforces 2195G，英文题名 Idiot First Search and Queries。