该问题与问题 E 共享定义。但是,它不要求相同的答案。
有一棵有 $$$n+1$$$ 个顶点的二叉树 ($$$n$$$ 是奇数),顶点标记为 $$$0,1,\ldots,n$$$。 最多一个字母 可以写入树的每个顶点,并且所有顶点最初都没有写入任何内容。树的根是顶点$$$0$$$。
在树中,顶点 $$$0$$$ 是顶点 $$$1$$$ 的父节点,而所有其他顶点都有 $$$2$$$ 子节点或 $$$0$$$ 子节点。
Bob 迷失在树的一个顶点中,并希望通过到达顶点 $$$0$$$ 来逃离树。这对于大多数有常识的人来说是很容易的。然而,由于鲍勃是个白痴,他创造了一种新的遍历树的方式;介绍“白痴优先搜索”。
当 Bob 位于顶点 $$$v$$$ ($$$1 \le v \le n$$$) 时,Bob 的运动确定如下:
- 如果顶点 $$$v$$$ 是叶子,则 Bob 总是 移动到 $$$v$$$ 的父级;否则,请检查接下来的几个条件。
- 如果顶点 $$$v$$$ 上没有写入任何内容,则 Bob 会写入 'L' 在顶点 $$$v$$$ 上并移动到 $$$v$$$ 的左子节点;
- 如果'L' 写在顶点 $$$v$$$ 上,Bob 覆盖它 到 'R' 并移至 $$$v$$$ 的右子节点;
- 如果'R' 写在顶点 $$$v$$$ 上,Bob 删除它 并移动到 $$$v$$$ 的父级。
Bob 移动到相邻顶点需要恰好 $$$1$$$ 秒,因此 Bob 将需要 $$$x$$$ 秒来执行 $$$x$$$ 移动。
已经证明,无论 Bob 从哪个顶点开始,Bob 都可以在有限(尽管可能大得难以解释)时间内到达顶点 $$$0$$$。我们不知道是谁证明了这一点;当然不可能是鲍勃,但它肯定是被证明的。
您需要回答以下类型的 $$$q$$$ 查询:
- $$$v\;k$$$:假设Bob从顶点$$$v$$$开始,执行后确定Bob所在的顶点 恰好 $$$k$$$ 移动 ($$$1 \le v \le n$$$)。
对于每个查询,令 $$$T_v$$$ 为从顶点 $$$v$$$ 到达顶点 $$$0$$$ 所需的时间。然后,保证每个查询都有$$$k \lt 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 \color{red}{ \lt } \min(10^9+7,T_{v_j})$$$)。
保证输入定义满足语句中给定条件的有效二叉树。
保证所有测试用例的$$$n$$$总和不超过$$$300\,001$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$400\,000$$$。
输出
对于每个测试用例,在单独的行上输出 $$$q$$$ 查询的答案。
示例
输入复制
31 10 01 05 52 30 04 50 00 03 63 83 114 75 87 72 34 50 06 70 00 00 01 92 183 113 123 135 77 17
输出复制
12 3 5 2 12 2 1 3 1 2 4
注意
在第一个测试用例中,只有两个顶点,顶点 $$$0$$$ 和顶点 $$$1$$$。显然,Bob 从顶点 $$$1$$$ 开始后,执行 $$$0$$$ 移动后,Bob 将位于顶点 $$$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{红色}{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$$$ 上开始后,当 Bob 在顶点 $$$3$$$ 上开始执行 $$$8$$$ 移动时,Bob 位于顶点 $$$3$$$ 上;
- Bob 在顶点 $$$3$$$ 上开始后,执行了 $$$11$$$ 移动后,Bob 位于顶点 $$$5$$$ 上。