# D. Arboris Contractio [문제 링크](https://codeforces.com/contest/2131/problem/D) ## Problem Statement Kagari is preparing to archive a tree, and she knows the cost of doing so will depend on its diameter (∗). 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: 1. Choose two vertices $s$ and $t$. Let the sequence of vertices on the simple path (†) from $s$ to $t$ be $v_0, v_1, \dots, v_k$, where $v_0 = s$ and $v_k = t$. 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)$. 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)$. It can be shown that the graph is still a tree after the operation. Help her determine the minimum number of operations required to achieve the minimal diameter. ## Input 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. 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. 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 \ne v$) that indicate an edge between vertex $u$ and $v$. It is guaranteed that these edges form a tree. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output one integer — the minimum number of operations to minimize the diameter. ## Footnotes (∗) 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. (†) 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. ## 풀이 #### 각 노드에서 총 리프 노드의 수 - 자식 중의 리프 노드의 수 - (자신이 리프 노드인지의 여부) 식을 이용하여 풀었다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; const int INF = 0x3f3f3f3f; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; vi inbound(n); vvi conn(n); for(int i=0;i<n-1;i++) { int u, v; cin >> u >> v; conn[u-1].push_back(v-1); conn[v-1].push_back(u-1); inbound[u-1]++; inbound[v-1]++; } int totalLeaf=0; for(int i=0;i<n;i++) { if(inbound[i]==1) totalLeaf++; } int minCnt = INF; for(int i=0;i<n;i++) { int cnt = totalLeaf; if(inbound[i]==1) cnt--; for(int next:conn[i]) { if(inbound[next]==1) cnt--; } minCnt = min(minCnt, cnt); } cout << minCnt << '\n'; } } ```