#P17547. [JAG 2026 Summer Camp #2] Tree + 1
[JAG 2026 Summer Camp #2] Tree + 1
题目描述
给定一棵有 个顶点的树,顶点编号为 到 。
你的目标是按照以下步骤,让这棵树的每个顶点都被访问至少一次。
- 任意选择两个顶点,在它们之间添加一条边。
- 任意选择一个顶点,并访问它。
- 将以下操作重复任意多次:从与当前访问的顶点有边相连的顶点中任意选择一个,并访问该顶点。每次操作的代价为 。
求达成目标所需的最小总代价。
输入格式
输入包含一组或多组测试数据。第一行包含一个整数 (),表示测试数据组数。每组测试数据的格式如下:
N
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}
整数 ()表示给定树的顶点数。
对于每个整数 (),整数 表示第 条边的两个端点的编号。
给定的图构成一棵树。
所有测试数据的 之和不超过 。
输出格式
对于每组测试数据,输出达成目标所需的最小总代价。
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
提示
对于第一组测试数据,在顶点 和 之间添加一条边后,可以从顶点 出发,按 的顺序访问顶点,总代价为 。