CF2195G Idiot First Search and Queries

本题与 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$。

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

在第一个测试用例中，只有两个顶点，顶点 $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 翻译