E3. 数字村庄（极限版本）详细题解

1. 问题重述与约束

• $n, m \le 2\times 10^5$，$\sum n, \sum m \le 2\times 10^5$。
• 需要为每个 $k = 1 \dots n$ 输出最小总延迟。
• 与 Easy/Hard 版本不同，这里 $n$ 很大，$O(n^2)$ 不可行，需要 $O(n \log n)$ 或 $O(n \log m)$ 的算法。

---

2. 核心转化：Kruskal 重构树（KRT）

由于路径代价是路径上的最大边权，我们可以使用类似 Kruskal 的算法构建可达性树（Reachability Tree）：

• 初始时，图没有边，每个顶点是一个连通分量。
• 按边权 $w_i$ 升序加入边，每次合并两个连通分量时，创建一个新节点作为这两个分量根的父亲，新节点的权值为 $w_i$。
• 最终得到一棵有 $2n-1$ 个节点的二叉树（KRT），叶子节点对应原图顶点，内部节点对应 MST 的边。

性质：在原图中，任意两个叶子节点 $u,v$ 之间路径的最大边权等于它们在 KRT 中 LCA 的权值。

---

3. 问题转化到 KRT 上

• 标记需要互联网的叶子节点为 特殊叶子。
• 对于每个节点 $x$，定义 $cnt[x]$ = 子树 $x$ 中特殊叶子的数量。

假设我们选择了 $k$ 个服务器（放在某些叶子节点上）。在 KRT 中，考虑这些服务器叶子节点的所有祖先，它们形成一个连通子树（包含根）。每个特殊叶子会连接到它最近的、在这个子树中的祖先，代价为该祖先的权值。

因此，问题等价于：

• 在 KRT 中，选择 $k$ 个叶子作为服务器。
• 定义“目标节点”为每个特殊叶子到最近服务器祖先路径上的第一个祖先（即 LCA 路径上的最低服务器祖先）。
• 总代价 = 所有目标节点的权值之和。

---

4. 转化为树上的“叶子删除”操作

考虑另一种视角：初始时，我们假设每个特殊叶子自己就是服务器（即 $k = n$ 时，每个特殊叶子放一个服务器）。此时总代价为 $0$（因为每个特殊叶子目标是自己，权值为 $0$）。

当我们减少服务器数量时（即从 $k+1$ 个服务器减少到 $k$ 个），相当于在 KRT 中删除一个叶子节点（该叶子原本是服务器），并将该叶子下的所有目标节点上移到其父节点。

删除操作的成本：

• 设被删除的叶子节点为 $x$，其父节点为 $y$，权值分别为 $val[x]$ 和 $val[y]$。
• 删除 $x$ 后，原本以 $x$ 为目标的特殊叶子（即 $x$ 子树内的所有特殊叶子）现在改为以 $y$ 为目标。
• 每个特殊叶子的代价增加 $(val[y] - val[x])$。
• 因此删除 $x$ 的总成本为：$$\text{cost} = (val[y] - val[x]) \times cnt[x]$$ 其中 $cnt[x]$ 是 $x$ 子树内的特殊叶子数。

---

5. 边权定义

定义每条边 $(x \to y)$（其中 $y$ 是 $x$ 的父节点）的长度为：

$$\text{len}(x, y) = (val[y] - val[x]) \times cnt[x] $$

那么：

• 初始状态（$k = n$ 个服务器）总代价为 $0$。
• 每次删除一个叶子节点 $x$，总代价增加 $\text{len}(x, y)$。
• 删除后，$x$ 的父节点 $y$ 成为新的叶子（如果 $y$ 的所有子节点都被删除了）。
• 最终，当我们只剩下 $k$ 个叶子节点（服务器）时，总代价就是所有被删除边的长度之和。

目标：对于每个 $k$，找到一种删除 $n - k$ 条边的方案，使得总代价最小。

等价地，我们希望保留 $k$ 条从根到叶子的路径（即保留 $k$ 个叶子），使得保留的边的总长度最大（因为总代价 = 所有边总长度 - 保留边总长度，而所有边总长度是固定的）。

---

6. 贪心策略

问题转化为：在 KRT 中，选择 $k$ 条从根到叶子的不相交路径（它们可以共享祖先），使得这些路径的边权和最大。

这是一个经典的树上选 $k$ 条路径问题，可以用贪心解决：

• 每次选择当前最长的可用路径（从某个节点到其子树中最深的叶子）。
• 选择后，将该路径上的节点标记为“已使用”，并更新其他路径的长度。

具体实现：

• 对每个节点 $x$，维护 best[x] = 从 $x$ 出发到其子树中某个特殊叶子的最长路径长度。
• 初始时，best[x] = max(best[l], best[r]) + len(x, child)，但这里长度是边权。
• 用一个优先队列（最大堆）存储所有当前可用的路径长度。
• 每次取出最大值，累加到答案中，然后分裂该路径：将该节点的两个孩子的最长路径加入队列（因为选择该路径后，该节点被占用，其子节点可以开始新的路径）。

---

7. 具体算法步骤

1. 建 MST（Kruskal）。
2. 建 Kruskal 重构树（KRT），得到 $2n-1$ 个节点。
3. 计算每个节点的 $cnt[x]$（子树内特殊叶子数）。
4. 计算每条边 $(x \to y)$ 的长度：$$\text{len}[x] = (val[y] - val[x]) \times cnt[x]$$
5. 从根开始 DFS，计算每个节点的最长路径长度 down[x]：
   • 叶子节点：down[x] = 0
   • 内部节点：down[x] = max(down[l], down[r]) + len[x]，其中 len[x] 是 $x$ 到父节点的边权（根节点没有父节点，特殊处理）。
6. 使用优先队列（最大堆）维护所有可用的路径：
   • 初始时，将 down[root] 加入堆。
   • 重复 $n$ 次（或直到堆空）：
     • 取出最大值 cur，累加到答案数组 ans[k]（表示当剩余 $k$ 个叶子时的最大保留边权和）。
     • 如果该路径来自节点 $x$，将 down[l] 和 down[r] 加入堆（如果存在）。
7. 最终答案：
   • 总代价 = 所有边总长度 - 保留边总长度。
   • 但注意，初始总代价为 $0$ 对应 $k = n$，我们计算的是减少代价。
   • 更直接：ans[k] 就是当保留 $k$ 个叶子时的最小总延迟。

---

8. 时间复杂度

• 建 MST：$O(m \log m)$
• 建 KRT：$O(m \log n)$
• DFS 和优先队列：$O(n \log n)$
• 总复杂度：$O((n + m) \log (n + m))$，满足约束。

---

9. 结论

该问题通过 Kruskal 重构树 + 贪心路径选择 在 $O((n+m)\log(n+m))$ 时间内解决，适用于 $n, m \le 2\times 10^5$ 的极限版本。