题目重述

我们有一棵 $n$ 个结点的树。
每次操作：选择 $s$ 和 $t$，把 $s$ 到 $t$ 的唯一路径上的所有点（除了 $s$）直接连接为 $s$ 的孩子（即删除原路径上的边，添加 $s$ 到这些点的边）。
问：最少需要多少次操作，才能使得树的直径最小？

---

关键观察

1. $n = 2$ 时
   直径已经是 $1$，不需要操作，答案为 $0$。

2. $n > 2$ 时
   可以证明最小的直径只能是 $2$。
   为什么？
   因为我们可以任选一个根 $r$，然后反复操作使其它所有结点都直接成为 $r$ 的孩子（即深度为 $1$），这样任意两个叶子之间的距离最多为 $2$（经过 $r$）。
   所以最小直径可达 $2$。

   因此，问题转化为：通过最少操作，使所有结点深度 ≤ 1（相对于某根 $r$）。

---

操作与深度的关系

固定根 $r$，定义：

• $d_u$：$u$ 在树中的深度（$d_r = 0$，孩子深度 $=$ 父深度 $+1$）。
• 初始树中，深度 $> 1$ 的结点需要被“拉”到深度 $1$。

在一次操作中：

• 选择路径 $s \to t$，删除路径上的边，再把 $t$ 及其中间结点连到 $s$。
• 注意：一次操作只能让路径末端的一个叶子（以及中间结点）提升到离 $s$ 更近的位置。
• 实际上，一次操作最多可以将一条从 $r$ 出发到某个深度 $>1$ 的叶子的路径上的所有点变为 $r$ 的直接孩子。

因此：

• 对于深度 $>1$ 的叶子，每个这样的叶子至少需要一次操作（才能让它成为 $r$ 的孩子）。
• 一次操作可以处理一条从 $r$ 出发的路径上多个深度 >1 的点，但只能消除一个深度 >1 的叶子（因为路径末端必须是叶子）。

结论：
若固定根 $r$，最少操作数 = 深度 $> 1$ 的叶子数量。

---

优化根的选择

因为我们可以自由选择 $r$，所以要最小化：

$$\text{操作数} = \min_{r} \left( \text{深度} > 1 \text{ 的叶子数} \right) $$

---

等价转换

深度 $>1$ 的叶子 = 叶子总数 − 深度 $=1$ 的叶子。

而深度 $=1$ 的叶子就是根 $r$ 的邻居中为叶子的那些结点。
设 $c_1$ = 整棵树叶子总数。
设 $m_r$ = 根 $r$ 的邻居中叶子的数量。

那么对于根 $r$，操作数 = $c_1 - m_r$。

所以：

$$\text{答案} = c_1 - \max_{r} m_r$$

其中 $m_r$ = 与 $r$ 相邻的叶子结点数。

---

最终解法

1. 读入树，计算每个结点的度数 $\deg(u)$。
2. 叶子结点定义为 $\deg(u) = 1$。
3. 计算 $c_1$ = 叶子总数。
4. 对每个结点 $u$，计算 $m_u$ = 它的邻居中是叶子的数量。
5. 取 $m_{\max} = \max_u m_u$。
6. 答案 = $c_1 - m_{\max}$。
7. 特判 $n \le 3$ 时答案为 $0$（因为此时直径已经 ≤ 2）。

---

示例验证

以第一个样例（$n=4$，边：1-2, 1-3, 2-4）为例：

• 叶子：3, 4 → $c_1 = 2$
• 结点 1：邻居 2(度2), 3(度1) → $m_1 = 1$
• 结点 2：邻居 1(度2), 4(度1) → $m_2 = 1$
• 结点 3：邻居 1(度2) → $m_3 = 0$
• 结点 4：邻居 2(度2) → $m_4 = 0$
• $m_{\max} = 1$
• 答案 = $2 - 1 = 1$

符合题目输出。

---

复杂度

• 每个结点遍历邻居一次。
• 总复杂度 $O(n)$。
• 满足所有测试用例 $n$ 总和 ≤ $2\times 10^5$。

---

对应 Python 标程思路

c1 = sum(deg[u] == 1 for u in range(n))
mx = max(sum(deg[v] == 1 for v in g[u]) for u in range(n))
return c1 - mx if n > 3 else 0

完全符合上述推导。