33OJ
登录 注册

#P17547. [JAG 2026 Summer Camp #2] Tree + 1

[JAG 2026 Summer Camp #2] Tree + 1

Problem Description

You are given a tree with NN vertices numbered from 11 to NN.

Your goal is to visit every vertex of this tree at least once by following the steps below.

  1. Choose any two vertices and add an edge connecting them.
  2. Choose any one vertex and visit it.
  3. 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 11.

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 tt (1≤t≤1051\le t\le 10^5), the number of test cases. Each of the tt 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 NN (2≤N≤5×1052\le N\le 5\times 10^5) represents the number of vertices in the given tree.

For each integer ii (1≤i≤N−11\le i\le N-1), the integers uiu_i and viv_i represent the vertex numbers of the endpoints of the ii-th edge.

The given graph forms a tree.

The sum of NN over all test cases does not exceed 5×1055\times 10^5.

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 44 and 66, you can start at vertex 11 and visit the vertices in the order 1→2→3→4→6→51\to 2\to 3\to 4\to 6\to 5, for a total cost of 55.