2195E.md (3924B)
1 Source: https://codeforces.com/problemset/problem/2195/E 2 3 E. Idiot First Search 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 In the tree, vertex $0$ is the parent of vertex $1$, while all other vertices have either $2$ children or $0$ children. 24 25 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". 26 27 When Bob is on vertex $v$ ($1 \le v \le n$), Bob's movement is determined as follows: 28 29 * If vertex $v$ is a leaf, Bob always moves to the parent of $v$; otherwise, check the next few conditions. 30 * If nothing is written on vertex $v$, Bob writes 'L' on vertex $v$ and moves to the left child of $v$; 31 * If 'L' is written on vertex $v$, Bob overwrites it to 'R' and moves to the right child of $v$; 32 * If 'R' is written on vertex $v$, Bob erases it and moves to the parent of $v$. 33 34 It takes exactly $1$ second for Bob to move to an adjacent vertex, so Bob will take exactly $x$ seconds to perform $x$ moves. 35 36 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. 37 38 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$. 39 40 Input 41 42 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. 43 44 The first line of each test case contains a single integer $n$ ($1 \le n \le 300\,001$, $n$ is odd). 45 46 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$). 47 48 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$. 49 50 It is guaranteed that the input defines a valid binary tree satisfying the conditions given in the statement. 51 52 It is guaranteed that the sum of $n$ over all test cases does not exceed $300\,001$. 53 54 Output 55 56 For each test case, output $n$ integers $\tau_1,\tau_2,\ldots,\tau_n$ separated by spaces. 57 58 Here, $\tau_k$ denotes the total time it takes to reach vertex $0$ if Bob started on vertex $k$, modulo $10^9+7$. 59 60 Example 61 62 Input 63 64 ``` 65 3 66 67 1 68 69 0 0 70 71 5 72 73 2 3 74 75 0 0 76 77 4 5 78 79 0 0 80 81 0 0 82 83 7 84 85 2 3 86 87 4 5 88 89 0 0 90 91 6 7 92 93 0 0 94 95 0 0 96 97 0 0 98 ``` 99 100 Output 101 102 ``` 103 1 104 105 9 10 14 15 15 106 107 13 22 14 27 23 28 28 108 ``` 109 110 Note 111 112 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$. 113 114 On the second test case, the tree is given as follows. 115 116  117 118 It takes $14$ seconds for Bob to reach vertex $0$ from vertex $3$. The moves are as follows: 119 120 $$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$$ 121 122 Here, the letters above the arrows denote the letter on the vertex before moving to the adjacent vertex, where $\mathtt{X}$ denotes nothing written.