2131D.md (2963B)
1 Source: https://codeforces.com/problemset/problem/2131/D 2 3 D. Arboris Contractio 4 5 time limit per test 6 7 2 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 Kagari is preparing to archive a tree, and she knows the cost of doing so will depend on its diameter$^{\text{∗}}$. To keep the expense down, her goal is to shrink the diameter as much as possible first. She can perform the following operation on the tree: 22 23 1. Choose two vertices $s$ and $t$. Let the sequence of vertices on the simple path$^{\text{†}}$ from $s$ to $t$ be $v_0, v_1, \dots, v_k$, where $v_0 = s$ and $v_k = t$. 24 2. Remove all edges along the path. In other words, remove edges $(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$. 25 3. Connect vertices $v_1, v_2, \dots, v_k$ directly to $v_0$. In other words, add edges $(v_0, v_1), (v_0, v_2), \dots, (v_0, v_k)$. 26 27 It can be shown that the graph is still a tree after the operation. 28 29 Help her determine the minimum number of operations required to achieve the minimal diameter. 30 31 $^{\text{∗}}$The diameter of a tree is the longest possible distance between any pair of vertices. The distance itself is measured by the number of edges on the unique simple path connecting them. 32 33 $^{\text{†}}$A simple path is a path between two vertices in a tree that does not visit any vertex more than once. It can be shown that the simple path between any two vertices is always unique. 34 35 Input 36 37 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. 38 39 The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of the vertices in the tree. 40 41 The following $n-1$ lines of each test case describe the tree. Each of the lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) that indicate an edge between vertex $u$ and $v$. It is guaranteed that these edges form a tree. 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, output one integer — the minimum number of operations to minimize the diameter. 48 49 Example 50 51 Input 52 53 ``` 54 4 55 56 4 57 58 1 2 59 60 1 3 61 62 2 4 63 64 2 65 66 2 1 67 68 4 69 70 1 2 71 72 2 3 73 74 2 4 75 76 11 77 78 1 2 79 80 1 3 81 82 2 4 83 84 3 5 85 86 3 8 87 88 5 6 89 90 5 7 91 92 7 9 93 94 7 10 95 96 5 11 97 ``` 98 99 Output 100 101 ``` 102 1 103 0 104 0 105 4 106 ``` 107 108 Note 109 110 In the first test case, the diameter of the original tree is $3$. Kagari can perform an operation on $s = 3$ and $t = 4$. As the figure depicts, the operations includes the following steps: 111 112 1. Remove edges $(3, 1)$, $(1, 2)$ and $(2, 4)$. 113 2. Add edges $(3, 1)$, $(3, 2)$ and $(3, 4)$. 114 115  116 117 After the operation, the diameter reduces to $2$. It can be shown that $2$ is the minimum diameter. 118 119 In the second test case, the diameter of the tree is $1$. It can be shown that $1$ is already the minimum, so Kagari can perform no operation.