CF2195E Idiot First Search

有一棵包含 $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$ 取模。

对于第一组样例，只有两个结点：结点 $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 翻译