← 返回题目列表

Codeforces · 2195/G

G. 白痴优先搜索和查询

中文机器翻译题面 查看原题

该问题与问题 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$$$ 查询的答案。

示例

输入
复制

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$$$ 移动后,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$$$ 上。