310887: CF1905B. Begginer's Zelda
Description
You are given a tree$^{\dagger}$. In one zelda-operation you can do follows:
- Choose two vertices of the tree $u$ and $v$;
- 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$.
Determine the minimum number of zelda-operations required for the tree to have only one vertex.
$^{\dagger}$A tree is a connected acyclic undirected graph.
InputEach 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.
The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the number of vertices.
$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.
It is guaranteed that the given edges form a tree.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
OutputFor each test case, output a single integer — the minimum number of zelda-operations required for the tree to have only one vertex.
ExampleInput4 4 1 2 1 3 3 4 9 3 1 3 5 3 2 5 6 6 7 7 8 7 9 6 4 7 1 2 1 3 2 4 4 5 3 6 2 7 6 1 2 1 3 1 4 4 5 2 6Output
1 3 2 2Note
In the first test case, it's enough to perform one zelda-operation for vertices $2$ and $4$.
In the second test case, we can perform the following zelda-operations:
- $u = 2, v = 1$. Let the resulting added vertex be labeled as $w = 10$;
- $u = 4, v = 9$. Let the resulting added vertex be labeled as $w = 11$;
- $u = 8, v = 10$. After this operation, the tree consists of a single vertex.
Output
输入数据格式:第一行包含一个整数t,表示测试用例的数量。每个测试用例首先包含一个整数n,表示节点的数量,接下来n-1行,每行包含两个整数ui和vi,表示节点ui和节点vi之间有一条边。
输出数据格式:对于每个测试用例,输出一个整数,表示将树压缩为一个节点所需的最少操作次数。题目大意:给定一棵树,每次操作可以选择两个节点u和v,并将u到v的路径上的所有节点压缩为一个新节点w,求将这棵树压缩为一个节点所需的最少操作次数。 输入数据格式:第一行包含一个整数t,表示测试用例的数量。每个测试用例首先包含一个整数n,表示节点的数量,接下来n-1行,每行包含两个整数ui和vi,表示节点ui和节点vi之间有一条边。 输出数据格式:对于每个测试用例,输出一个整数,表示将树压缩为一个节点所需的最少操作次数。