← 返回题目列表

Codeforces · 2195/E

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$$$。我们不知道是谁证明了这一点;当然不可能是鲍勃,但它肯定是被证明的。

对于每个顶点 $$$k=1,2,\ldots,n$$$,请确定如果 Bob 从顶点 $$$k$$$ 开始,到达顶点 $$$0$$$ 所需的总时间(以秒为单位)。由于这些值可能很大,因此您只需计算它们对 $$$10^9+7$$$ 取模即可。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300\,001$$$, $$$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$$$ 的左子节点和右子节点。

保证输入定义满足语句中给定条件的有效二叉树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$300\,001$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数 $$$\tau_1,\tau_2,\ldots,\tau_n$$$ 以空格分隔。

这里,$$$\tau_k$$$ 表示如果 Bob 从顶点 $$$k$$$ 开始,到达顶点 $$$0$$$ 所需的总时间,以 $$$10^9+7$$$ 为模。

示例

输入
复制

3
1
0 0
5
2 3
0 0
4 5
0 0
0 0
7
2 3
4 5
0 0
6 7
0 0
0 0
0 0

输出
复制

1
9 10 14 15 15
13 22 14 27 23 28 28

注意

在第一个测试用例中,只有两个顶点,顶点 $$$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}} 2 \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{R}} 3 \xrightarrow{\mathtt{L}} 4 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{R}} 5 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{X}} 0$$

这里,箭头上方的字母表示移动到相邻顶点之前该顶点上的字母,其中 $$$\mathtt{X}$$$ 表示没有写入任何内容。