CF2195E.Idiot First Search

There is a binary tree of $n+1$ vertices ($n$ is odd), with vertices labeled $0,1,\ldots,n$. At most one letter can be written on each vertex of the tree, and all vertices initially have nothing written on them. The root of the tree is vertex $0$.

In the tree, vertex $0$ is the parent of vertex $1$, while all other vertices have either $2$ children or $0$ children.

Bob is lost in one vertex of the tree and wishes to escape the tree by reaching vertex $0$. This is very easy for most people with common sense. However, since Bob is an idiot, he created a new way of traversing the tree; introducing the "Idiot First Search".

When Bob is on vertex $v$ ($1 \le v \le n$), Bob's movement is determined as follows:

• If vertex $v$ is a leaf, Bob always moves to the parent of $v$; otherwise, check the next few conditions.
• If nothing is written on vertex $v$, Bob writes 'L' on vertex $v$ and moves to the left child of $v$;
• If 'L' is written on vertex $v$, Bob overwrites it to 'R' and moves to the right child of $v$;
• If 'R' is written on vertex $v$, Bob erases it and moves to the parent of $v$.

It takes exactly $1$ second for Bob to move to an adjacent vertex, so Bob will take exactly $x$ seconds to perform $x$ moves.

It has been shown that regardless of which vertex Bob starts on, Bob can reach vertex $0$ in a finite (though possibly inexplicably large) amount of time. We don't know who proved it; surely it can't be Bob, but it is definitely proven.

For each vertex $k=1,2,\ldots,n$, please determine the total time it takes to reach vertex $0$ if Bob started on vertex $k$, in seconds. As the values may be huge, you are only asked to compute them modulo $10^9+7$.

存在一棵含有 $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$ 取模后的值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 300\,001$, $n$ is odd).

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ denoting the children of vertex $i$ ($0 \le l_i,r_i \le n$).

For each vertex, $l_i=r_i=0$ is given if the vertex has no children. Otherwise, $l_i$ and $r_i$ are the left and right children of vertex $i$.

It is guaranteed that the input defines a valid binary tree satisfying the conditions given in the statement.

It is guaranteed that the sum of $n$ over all test cases does not exceed $300\,001$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 分别为其左子节点和右子节点。

保证输入所定义的是一棵满足题目所述条件的有效二叉树。

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

For each test case, output $n$ integers $\tau_1,\tau_2,\ldots,\tau_n$ separated by spaces.

Here, $\tau_k$ denotes the total time it takes to reach vertex $0$ if Bob started on vertex $k$, modulo $10^9+7$.

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

其中，$\tau_k$ 表示若 Bob 从顶点 $k$ 出发，到达顶点 $0$ 所需的总时间（对 $10^9+7$ 取模）。

On the first test case, there are only two vertices, vertex $0$ and vertex $1$. It takes only $1$ second for Bob to reach vertex $0$ from vertex $1$.

On the second test case, the tree is given as follows.

It takes $14$ seconds for Bob to reach vertex $0$ from vertex $3$. The moves are as follows:

$$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$$

Here, the letters above the arrows denote the letter on the vertex before moving to the adjacent vertex, where $\mathtt{X}$ denotes nothing written.

在第一个测试用例中，图中仅有两个顶点：顶点 $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}$ 表示该顶点上未写任何字母。