E2. 数字村庄（困难版本）详细题解

1. 问题重述与约束变化

• 与 Easy Version 相比，n, m 最大可达 5000，且 $\sum n \le 5000$，$\sum m \le 5000$。
• 因此 $O(n^2)$ 的算法可行，$O(n^3)$ 不可行。
• 仍需要为每个 $k = 1 \dots n$ 输出最小总延迟。

2. 问题转化（与 Easy Version 相同）

1. 最小瓶颈路径：
   两点间路径的最大边权的最小值 = 最小生成树（MST）上路径的最大边权。

2. Kruskal 重构树：
   按边权升序构建重构树，叶子是原图顶点，内部节点权值 = 对应边权。
   性质：原树中两点 $u,v$ 路径的最大边权 = KRT 中 $\text{LCA}(u,v)$ 的权值。

3. 设 $P$ 为需要互联网的顶点集（$|P| = p$）。
   选择服务器集合 $S$（$|S| \le k$），则总延迟：

   $$\text{cost}(S) = \sum_{u \in P} \min_{s \in S} \text{maxEdge}(u,s) $$

   其中 $\text{maxEdge}(u,s)$ 在 KRT 中等于 $\text{val}[\text{LCA}(u,s)]$。

3. 关键观察：子树覆盖思想

在 KRT 中，考虑一个内部节点 $x$（对应一条边权 $w$），它把树分成若干子树（KRT 是二叉树，但原 MST 是多叉树，KRT 将 MST 边转化为内部节点）。

实际上，KRT 中每个内部节点 $x$ 代表原 MST 的一条边，它将原 MST 分成两个连通块。
设 $x$ 的两个孩子子树为 $L$ 和 $R$，其中包含的 $P$ 中点数量分别为 $c_L$ 和 $c_R$。

重要性质：
如果 $L$ 和 $R$ 中都有服务器，则 $x$ 对应的边权 $w$ 不会被任何 $P$ 中点计入延迟（因为每个点可以连接到同侧的服务器，不跨过 $x$）。
如果只有一侧有服务器，则另一侧的所有 $P$ 点必须跨过 $x$ 连接到对面，因此它们的延迟至少为 $w$，且这部分贡献恰好为 $w \times$（另一侧的 $P$ 点数）。

4. 动态规划设计（基于 KRT）

定义 $dp[u][t]$ = 在 KRT 的子树 $u$ 中，放置恰好 $t$ 个服务器，且子树 $u$ 内部的所有 $P$ 点都被覆盖时，这些 $P$ 点的最小总延迟。

• 对于叶子节点 $u$：

  • 如果 $u \in P$：$dp[u][1] = 0$（放一个服务器，延迟 0），$dp[u][0] = \infty$（不放服务器无法覆盖）。
  • 如果 $u \notin P$：$dp[u][0] = 0$，$dp[u][1] = 0$（放服务器不影响）。

• 对于内部节点 $u$，有两个孩子 $l$ 和 $r$，边权 $w = val[u]$。
  设 $c_l, c_r$ 为子树内 $P$ 点数量。
  枚举 $l$ 中放 $a$ 个服务器，$r$ 中放 $b$ 个，总 $t = a + b$。
  转移时需要考虑跨子树的贡献：

  • 如果 $a > 0$ 且 $b = 0$，则 $r$ 中的 $c_r$ 个点必须跨过 $u$ 连接到 $l$ 的服务器，贡献 $w \times c_r$。
  • 如果 $a = 0$ 且 $b > 0$，则贡献 $w \times c_l$。
  • 如果 $a > 0$ 且 $b > 0$，则贡献 $0$（两侧内部覆盖）。
  • 如果 $a = 0$ 且 $b = 0$，则无法覆盖（除非 $c_l = c_r = 0$，但这种情况不需考虑）。

  因此：

  $$dp[u][t] = \min_{a+b=t} \left( dp[l][a] + dp[r][b] + w \cdot \text{cross}(a,b) \right) $$

  其中

  $$\text{cross}(a,b) = \begin{cases} c_r & \text{if } a > 0, b = 0 \\ c_l & \text{if } a = 0, b > 0 \\ 0 & \text{if } a > 0, b > 0 \\ \infty & \text{if } a = 0, b = 0 \text{ 且 } c_l + c_r > 0 \end{cases} $$

5. 算法步骤

1. 读入图，建 MST（Kruskal，$O(m \log m)$）。
2. 建 Kruskal 重构树（$O(n \log n)$）。
3. 在 KRT 上树形 DP：
   • 自底向上计算 $c_u$ = 子树内 $P$ 点数。
   • 对每个节点 $u$，$dp[u]$ 是一个长度为 $c_u+1$ 的数组（$dp[u][0]$ 可能为 $\infty$）。
   • 合并时使用卷积技巧，但这里 $c_u$ 总和 $\le n$，直接 $O(c_l \cdot c_r)$ 合并即可，总复杂度 $O(n^2)$。
4. 答案：对于每个 $k = 1 \dots n$，$ans[k] = dp[root][\min(k, p)]$，因为放多于 $p$ 个服务器无意义（每个 $P$ 点放一个即可）。

6. 时间复杂度分析

• 建 MST：$O(m \log m)$
• 建 KRT：$O(m \log n)$
• DP 合并：每个节点合并的复杂度为 $O(c_l \cdot c_r)$，且 $\sum c_l \cdot c_r \le \frac{(\sum c_u)^2}{2} \le O(p^2) \le O(n^2)$。
• 总复杂度 $O(n^2)$，对于 $n \le 5000$ 可行。

7. 空间优化

• $dp[u]$ 只存长度为 $c_u+1$ 的数组。
• 合并后释放子节点的数组。
• 总空间 $O(n^2)$ 约 $25 \times 10^6$ 个 long long，约 200MB，可能偏大。需要优化：
  • 使用 vector<ll> 且及时释放。
  • 或使用 short / int 存储（但 $w \le 10^9$，乘积可能超 int，需 long long）。
  • 实际 $n=5000$ 时 $p$ 也 $\le 5000$，最坏情况 $p=n$，此时 $c_l \cdot c_r$ 总和约 $\frac{n^2}{2}$，DP 总状态数 $O(n^2)$，但每个状态只存一个 ll，约 $25\times 10^6 \times 8$ = 200MB，加上递归开销可能接近极限。
    可行方案：使用 vector<long long> 并只存必要状态，或采用分治 DP 减少内存。

8. 优化内存的实现技巧

使用 DFS 后序，每次合并后立即释放子节点的 dp 数组，这样任意时刻只有一条路径上的 dp 数组同时存在，总内存 $O(n \cdot \text{max\_c})$，最坏 $O(n^2)$ 但常数小很多。

9. 最终结论

该问题可通过 MST + Kruskal 重构树 + 树形背包 DP 在 $O(n^2)$ 时间和 $O(n^2)$ 空间内解决，适用于 $n \le 5000$ 的困难版本。