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  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.