codeforces-scrape

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

1830A.md (2077B)


      1 Source: https://codeforces.com/problemset/problem/1830/A
      2 
      3 A. Copil Copac Draws Trees
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Copil Copac is given a list of $n-1$ edges describing a tree of $n$ vertices. He decides to draw it using the following algorithm:
     22 
     23 * Step $0$: Draws the first vertex (vertex $1$). Go to step $1$.
     24 * Step $1$: For every edge in the input, in order: if the edge connects an already drawn vertex $u$ to an undrawn vertex $v$, he will draw the undrawn vertex $v$ and the edge. After checking every edge, go to step $2$.
     25 * Step $2$: If all the vertices are drawn, terminate the algorithm. Else, go to step $1$.
     26 
     27 The number of readings is defined as the number of times Copil Copac performs step $1$.
     28 
     29 Find the number of readings needed by Copil Copac to draw the tree.
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows.
     34 
     35 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices of the tree.
     36 
     37 The following $n - 1$ lines of each test case contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$) — indicating that $(u_i,v_i)$ is the $i$-th edge in the list. It is guaranteed that the given edges form a tree.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, output the number of readings Copil Copac needs to draw the tree.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 2
     51 
     52 6
     53 
     54 4 5
     55 
     56 1 3
     57 
     58 1 2
     59 
     60 3 4
     61 
     62 1 6
     63 
     64 7
     65 
     66 5 6
     67 
     68 2 4
     69 
     70 2 7
     71 
     72 1 3
     73 
     74 1 2
     75 
     76 4 5
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 2
     83 3
     84 ```
     85 
     86 Note
     87 
     88 In the first test case:
     89 
     90 After the first reading, the tree will look like this:
     91 
     92  ![](https://espresso.codeforces.com/a21418b7e7255df911972587d36fbb2542abf923.png) 
     93 
     94 After the second reading:
     95 
     96  ![](https://espresso.codeforces.com/c9e842cefecc42a173634687c3d94e79776a237b.png) 
     97 
     98 Therefore, Copil Copac needs $2$ readings to draw the tree.