---

题意简述

我们有一棵有 $n$ 个节点的树，根节点为 $1$。
叶子 定义为：非根节点且度数为 $1$ 的节点。

一次操作可以移除一个叶子及其相连的边（移除后可能出现新的叶子）。

问：最少需要多少次操作，才能得到一棵仍然以 $1$ 为根的树，且这棵树的所有叶子到根的距离都相等。

---

第一步：转换问题

设最终所有叶子的深度为 $d$（根深度为 $0$ 或 $1$，通常用 $0$ 方便，但题目样例深度从 $1$ 开始，我们统一用根深度 $0$，距离从 $1$ 开始可等价）。

最终树必须满足：

1. 所有叶子深度 $= d$。
2. 根为 $1$，且 $1$ 在最终树中。

深度 $d$ 是固定的，那么哪些节点可以保留？

• 如果某个节点深度 $> d$，它不能保留（否则会产生深度更大的叶子）。
• 如果某个节点深度 $\le d$，但它所在子树的最大深度 $< d$，则它无法成为深度 $d$ 的叶子的祖先，也会被删掉。

---

定义：

• $a_u$ = 节点 $u$ 的深度（根深度 $0$）。
• $b_u$ = 节点 $u$ 的子树中节点的最大深度。

那么节点 $u$ 在最终深度为 $d$ 的树中 存活 的条件是：

$$a_u \le d \quad \text{且} \quad b_u \ge d$$

解释：

• $a_u \le d$：节点深度不能超过目标深度。
• $b_u \ge d$：子树中至少有一个深度 $\ge d$ 的节点，这样才能让深度 $d$ 的叶子在该子树中。

---

第二步：存活节点数

对于给定的 $d$，存活节点数 $S(d)$ 就是满足上述条件的节点数。

我们要 删除的节点数 = $n - S(d)$。

因为我们要最少删除次数，即最大化 $S(d)$。

---

第三步：区间覆盖模型

对每个节点 $u$，它会在哪些 $d$ 中存活？

条件 $a_u \le d \le b_u$，即 $d$ 在区间 $[a_u, b_u]$ 内。

于是问题变为：

每个节点 $u$ 对应区间 $[a_u, b_u]$，
选择一个 $d$ 使得包含 $d$ 的区间数最大。
答案 = $n - \max_d (\text{包含 } d \text{ 的区间数})$。

---

第四步：如何求最大覆盖数

我们需要知道所有节点的 $a_u$ 和 $b_u$：

• $a_u$：BFS 或 DFS 从根计算深度。
• $b_u$：DFS 后序遍历，$b_u = \max(a_u, \max_{v \in \text{children}(u)} b_v)$。

然后对每个节点 $u$，它在区间 $[a_u, b_u]$ 的每个整数 $d$ 上加 $1$。

这可以用差分数组完成：
$diff[a_u] \ += 1$，$diff[b_u+1] \ -= 1$，然后前缀和得到每个 $d$ 的覆盖数。

$d$ 的取值范围：$0$ 到最大深度（$\le n$）。

---

第五步：答案计算

设 $cover[d]$ = 覆盖 $d$ 的区间数（即存活节点数）。

则 $\text{ans} = n - \max_{d \ge 0} cover[d]$。

---

第六步：复杂度

• 每个节点计算 $a_u, b_u$：$O(n)$
• 差分更新：每个节点 $O(1)$
• 前缀和：$O(\text{max depth}) \le O(n)$

总复杂度 $O(n)$，所有测试用例总 $n \le 5\cdot 10^5$，足够快。

---

第七步：验证样例

用第一个样例（$n=7$，根深度 $0$）：

1-2, 1-3, 2-4, 2-5, 4-6, 4-7

深度：

• a1=0, a2=1, a3=1, a4=2, a5=2, a6=3, a7=3

子树最大深度 b：

• b6=3, b7=3, b4=3, b5=2, b2=3, b3=1, b1=3

节点区间： 1: [0,3]
2: [1,3]
3: [1,1]
4: [2,3]
5: [2,2]
6: [3,3]
7: [3,3]

对每个 $d$ 覆盖数： d=0: {1} → 1
d=1: {1,2,3} → 3
d=2: {1,2,4,5} → 4
d=3: {1,2,4,6,7} → 5

最大覆盖 = 5（d=3）。
答案 = 7-5=2，匹配输出。

---

最终题解总结：

1. 计算每个节点的深度 $a_u$ 和子树最大深度 $b_u$。
2. 对每个节点，在区间 $[a_u, b_u]$ 上做差分加 $1$。
3. 前缀和得到每个 $d$ 的存活节点数。
4. 答案 = $n - \max(存活节点数)$。