codeforces-scrape

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

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