题目描述

有一棵包含 $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，但可以确信这一点。

对于每个点 $k=1,2,\ldots,n$，请计算如果 Bob 从结点 $k$ 出发，到达结点 $0$ 所需的总用时（单位：秒）。由于答案可能很大，只需输出对 $10^9+7$ 取模的结果。

输入格式

每组数据包含多组测试数据。第一行为测试组数 $t$（$1 \le t \le 10^4$）。每组测试数据描述如下：

每组测试数据的第一行包含一个正整数 $n$（$1 \le n \le 300001$，且 $n$ 为奇数）。

接下来 $n$ 行，每行两个整数 $l_i$ 与 $r_i$，表示第 $i$ 个结点的左、右孩子（$0 \le l_i, r_i \le n$）。

若结点 $i$ 没有孩子，则给出 $l_i=r_i=0$。否则，$l_i$ 和 $r_i$ 分别表示结点 $i$ 的左、右孩子。

保证每组数据表示的都是合法的二叉树，且满足题目所述所有条件。

保证所有测试数据中 $n$ 的总和不超过 $300001$。

输出格式

对于每组测试数据，输出 $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$$

上方箭头边的字母表示 Bob 移动前结点上的状态，其中 $\mathtt{X}$ 表示未写任何内容。

由 ChatGPT 5 翻译

来源

Codeforces 2195E，英文题名 Idiot First Search。