← 返回题目列表

Codeforces · 2131/D

D. 乔木收缩

中文机器翻译题面 查看原题

Kagari 正准备归档一棵树,她知道这样做的成本将取决于它的直径$$$^{\text{*}}$$$。为了降低成本,她的目标是首先尽可能缩小直径。她可以对树执行以下操作:

  1. 选择两个顶点 $$$s$$$ 和 $$$t$$$。设简单路径$$$^{\text{†}}$$$ 上从$$$s$$$ 到$$$t$$$ 的顶点序列为$$$v_0, v_1, \dots, v_k$$$,其中$$$v_0 = s$$$ 且$$$v_k = t$$$。
  2. 删除路径上的所有边。换句话说,删除边 $$$(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$$$。
  3. 将顶点 $$$v_1, v_2, \dots, v_k$$$ 直接连接到 $$$v_0$$$。换句话说,添加边 $$$(v_0, v_1), (v_0, v_2), \dots, (v_0, v_k)$$$。

可以看出,运算后的图仍然是一棵树。

帮助她确定实现最小直径所需的最少操作次数。

$$$^{\text{*}}$$$树的直径是任意一对顶点之间的最长可能距离。距离本身是通过连接它们的唯一简单路径上的边数来测量的。

$$$^{\text{†}}$$$简单路径是树中两个顶点之间的路径,不会多次访问任何顶点。可以证明,任意两个顶点之间的简单路径总是唯一的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中顶点的数量。

每个测试用例的以下 $$$n-1$$$ 行描述了树。每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),表示顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证这些边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——最小化直径的最小操作数。

示例

输入
复制

4
4
1 2
1 3
2 4
2
2 1
4
1 2
2 3
2 4
11
1 2
1 3
2 4
3 5
3 8
5 6
5 7
7 9
7 10
5 11

输出
复制

1
0
0
4

注意

在第一个测试用例中,原始树的直径为$$$3$$$。 Kagari 可以对 $$$s = 3$$$ 和 $$$t = 4$$$ 执行操作。如图所示,操作包括以下步骤:

  1. 删除边 $$$(3, 1)$$$、$$$(1, 2)$$$ 和 $$$(2, 4)$$$。
  2. 添加边 $$$(3, 1)$$$、$$$(3, 2)$$$ 和 $$$(3, 4)$$$。

手术后,直径减小到$$$2$$$。可以看出$$$2$$$是最小直径。

在第二个测试用例中,树的直径为$$$1$$$。可以看出$$$1$$$已经是最小值,所以Kagari不能执行任何操作。