33OJ
登录 注册

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

[JAG 2026 Summer Camp #2] Tree + 1

题目描述

给定一棵有 NN 个顶点的树,顶点编号为 11 到 NN。

你的目标是按照以下步骤,让这棵树的每个顶点都被访问至少一次。

  1. 任意选择两个顶点,在它们之间添加一条边。
  2. 任意选择一个顶点,并访问它。
  3. 将以下操作重复任意多次:从与当前访问的顶点有边相连的顶点中任意选择一个,并访问该顶点。每次操作的代价为 11。

求达成目标所需的最小总代价。

输入格式

输入包含一组或多组测试数据。第一行包含一个整数 tt(1≤t≤1051\le t\le 10^5),表示测试数据组数。每组测试数据的格式如下:

N
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}

整数 NN(2≤N≤5×1052\le N\le 5\times 10^5)表示给定树的顶点数。

对于每个整数 ii(1≤i≤N−11\le i\le N-1),整数 ui,viu_i,v_i 表示第 ii 条边的两个端点的编号。

给定的图构成一棵树。

所有测试数据的 NN 之和不超过 5×1055\times 10^5。

输出格式

对于每组测试数据,输出达成目标所需的最小总代价。

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

提示

对于第一组测试数据,在顶点 44 和 66 之间添加一条边后,可以从顶点 11 出发,按 1→2→3→4→6→51\to 2\to 3\to 4\to 6\to 5 的顺序访问顶点,总代价为 55。