codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/dfccc9cd793030983f22e97a4aefba2172a64dd9.png) 
    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.