#P17547. [JAG 2026 Summer Camp #2] Tree + 1
[JAG 2026 Summer Camp #2] Tree + 1
Problem Description
You are given a tree with vertices numbered from to .
Your goal is to visit every vertex of this tree at least once by following the steps below.
- Choose any two vertices and add an edge connecting them.
- Choose any one vertex and visit it.
- Repeat the following action any number of times: choose any one of the vertices adjacent by an edge to the vertex you are currently visiting, and visit that vertex. This action costs .
Find the minimum possible total cost required to achieve the goal.
Input Format
The input consists of one or more test cases. The first line of the input contains an integer (), the number of test cases. Each of the test cases is given in the following format:
N
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}
The integer () represents the number of vertices in the given tree.
For each integer (), the integers and represent the vertex numbers of the endpoints of the -th edge.
The given graph forms a tree.
The sum of over all test cases does not exceed .
Output Format
For each test case, output the minimum possible total cost required to achieve the goal.
3
6
1 2
2 3
3 4
2 5
5 6
6
6 3
1 4
5 1
3 1
2 3
10
1 5
4 8
9 1
3 5
3 2
7 3
1 6
10 3
1 4
5
5
12
Hint
For the first test case, after adding an edge connecting vertices and , you can start at vertex and visit the vertices in the order , for a total cost of .