codeforces-scrape

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

1905B.md (2273B)


      1 Source: https://codeforces.com/problemset/problem/1905/B
      2 
      3 B. Begginer's Zelda
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given a tree$^{\dagger}$. In one zelda-operation you can do follows:
     22 
     23 * Choose two vertices of the tree $u$ and $v$;
     24 * Compress all the vertices on the path from $u$ to $v$ into one vertex. In other words, all the vertices on path from $u$ to $v$ will be erased from the tree, a new vertex $w$ will be created. Then every vertex $s$ that had an edge to some vertex on the path from $u$ to $v$ will have an edge to the vertex $w$.
     25 
     26  ![](https://espresso.codeforces.com/addde5e950b38560bc9f7ca4f6262a1dde4ae6a9.png) Illustration of a zelda-operation performed for vertices $1$ and $5$. 
     27 
     28 Determine the minimum number of zelda-operations required for the tree to have only one vertex.
     29 
     30 $^{\dagger}$A tree is a connected acyclic undirected graph.
     31 
     32 Input
     33 
     34 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     35 
     36 The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the number of vertices.
     37 
     38 $i$-th of the next $n − 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n, u_i \ne v_i$) — the numbers of vertices connected by the $i$-th edge.
     39 
     40 It is guaranteed that the given edges form a tree.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     43 
     44 Output
     45 
     46 For each test case, output a single integer — the minimum number of zelda-operations required for the tree to have only one vertex.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 4
     54 
     55 4
     56 
     57 1 2
     58 
     59 1 3
     60 
     61 3 4
     62 
     63 9
     64 
     65 3 1
     66 
     67 3 5
     68 
     69 3 2
     70 
     71 5 6
     72 
     73 6 7
     74 
     75 7 8
     76 
     77 7 9
     78 
     79 6 4
     80 
     81 7
     82 
     83 1 2
     84 
     85 1 3
     86 
     87 2 4
     88 
     89 4 5
     90 
     91 3 6
     92 
     93 2 7
     94 
     95 6
     96 
     97 1 2
     98 
     99 1 3
    100 
    101 1 4
    102 
    103 4 5
    104 
    105 2 6
    106 ```
    107 
    108 Output
    109 
    110 ```
    111 1
    112 3
    113 2
    114 2
    115 ```
    116 
    117 Note
    118 
    119 In the first test case, it's enough to perform one zelda-operation for vertices $2$ and $4$.
    120 
    121 In the second test case, we can perform the following zelda-operations:
    122 
    123 1. $u = 2, v = 1$. Let the resulting added vertex be labeled as $w = 10$;
    124 2. $u = 4, v = 9$. Let the resulting added vertex be labeled as $w = 11$;
    125 3. $u = 8, v = 10$. After this operation, the tree consists of a single vertex.