E1. 数字村庄（简单版本）详细题解

1. 问题重述

• 有一个 $n$ 个顶点 $m$ 条边的连通简单图（$n \le 400$，$n-1 \le m \le 400$）。
• 有 $p$ 个特殊顶点（需要互联网的房屋）$s_1, s_2, \dots, s_p$。
• 我们可以选择至多 $k$ 个顶点放置服务器。
• 每个特殊顶点会连接到某个服务器，路径延迟定义为该路径上最大边权。
• 目标：最小化所有特殊顶点的延迟之和。

对每个 $k = 1, 2, \dots, n$ 输出最小总延迟。

---

2. 关键转化

如果我们固定了服务器集合 $S$（$|S| \le k$），那么对于一个特殊顶点 $u$，它的延迟为：

$$\min_{s \in S} \max_{e \in \text{path}(u, s)} w_e$$

这其实就是 $u$ 到 $S$ 的最小化最大边权，即：

$$d(u, S) = \min_{s \in S} \text{(minimum spanning tree path max edge weight)} $$

---

3. 最小瓶颈路径与 MST

在图论中，两点之间路径的最大边权的最小值，等于最小生成树（MST）上这两点之间路径的最大边权。
因为 MST 满足最小瓶颈路径性质。

所以我们可以先求出图的 MST，之后所有问题都在 MST 上考虑（$n-1$ 条边）。

---

4. 转化到树上

设 $T$ 为原图的 MST，边权为 $w_e$。

对于树上任意两点 $u,v$，定义：

$$\text{maxEdge}(u,v) = \max_{e \in \text{path}_T(u,v)} w_e $$

则 $u$ 到服务器集合 $S$ 的延迟为：

$$d(u,S) = \min_{s \in S} \text{maxEdge}(u,s)$$

---

5. 进一步转化：Kruskal 重构树（KRT）

Kruskal 重构树是解决这类“路径最大边权最小值”问题的标准工具。

构造方法（按边权升序）：

• 初始有 $n$ 个叶子节点，权值为 $0$（或 $-\infty$）。
• 每次合并两个连通块时，新建一个节点，权值为当前边权，作为这两个连通块根节点的父节点。
• 最终形成一棵 $2n-1$ 个节点的二叉树（或森林，但原图连通，所以是一棵树）。

性质：
在原树 $T$ 中，两点 $u,v$ 的路径最大边权等于它们在 KRT 中的 LCA 的权值。

因此：

$$\text{maxEdge}(u,v) = \text{val}[\text{LCA}_{\text{KRT}}(u,v)] $$

---

6. 问题转化为 KRT 上的问题

在 KRT 上，叶子节点是原图的顶点（$1..n$），内部节点对应原 MST 的边（按边权从小到大）。

设叶子集合 $P$ 为需要互联网的顶点（$p$ 个）。

选择 $k$ 个叶子作为服务器（也可以选内部节点吗？题目说服务器可以安装在任意房屋，即任意顶点，对应 KRT 的叶子节点）。
注意：服务器只能放在原图顶点，即 KRT 的叶子节点。

---

7. 动态规划思路（基于 KRT）

我们可以用树形 DP 解决：
设 $dp[u][t]$ 表示在 KRT 的子树 $u$ 中，放置恰好 $t$ 个服务器（在叶子节点），能覆盖的 $P$ 中顶点的最小总延迟。

但是这里延迟是“路径上最大边权”，在 KRT 中，如果某个 $P$ 中顶点 $x$ 被子树 $u$ 内的服务器覆盖，它的延迟就是 $x$ 到该服务器的 LCA 的权值，这个 LCA 一定在 $x$ 到 $u$ 的路径上。
这很复杂。

---

8. 经典转化：考虑每条边对答案的贡献

另一种更简单的方法（常见于此类问题）：

对于 MST 上的每条边 $e$（权值 $w$），如果把它删掉，树会分成两个连通块 $A$ 和 $B$。
如果 $A$ 中有服务器，$B$ 中也有服务器，那么这条边不会被任何 $P$ 中顶点跨过？等等，我们想的是：
一个 $P$ 中顶点的延迟，等于它到最近服务器的路径上最大边权。
所以最大边权就是路径上最重的那条边。

---

9. 等价于：每条边是否贡献到总延迟

对于一个 $P$ 中顶点 $u$，设它到最近服务器的路径为 $u \to s$，路径上的最大边权记为 $W_u$。
那么总延迟 = $\sum_{u \in P} W_u$。

我们考虑每条边 $e$（权值 $w$）被哪些 $u$ 的路径经过，并且 $w$ 是 $u$ 到其最近服务器的路径上的最大值。
这等价于：
在 KRT 中，从 $u$ 向上走到第一个权值大于等于 $w$ 的祖先？有点绕。

---

10. 更简洁的解法（官方常见做法）

由于 $n \le 400$，我们可以用最小化最大边权的聚类思想：

我们按边权升序排序 MST 的边。
假设我们想用 $k$ 个服务器覆盖所有 $P$，那么总延迟可以看成：
将 $P$ 划分成 $k$ 组，每组选一个服务器（可以是组内任意点），组内点到服务器的最大边权为该组的成本，总成本 = 各组成本之和。

但组内点到服务器的最大边权 = 该组在 MST 上的最小斯坦纳树的最大边权？
实际上，如果组内点集为 $Q$，最优服务器位置是 $Q$ 的中心（最小化到所有点的最大边权），这个中心就是 $Q$ 在 MST 上的最优点，可以证明中心在 $Q$ 的 MST 子图的中心（树的中心）。

---

11. 最终简化：二分 + 贪心

由于 $n$ 小，我们可以这样做：

1. 预处理任意两点 $u,v$ 的 $\text{maxEdge}(u,v)$（$O(n^2 \log n)$ 或 Floyd 在树上 $O(n^2)$）。
2. 问题变为：选 $k$ 个服务器，最小化 $\sum_{u \in P} \min_{s \in S} \text{maxEdge}(u,s)$。

这类似于 k-median 问题，但距离度量是 $\text{maxEdge}$。

由于 $n \le 400$，我们可以用 DP + 树形背包 在 KRT 上做：

• 在 KRT 上，每个内部节点 $v$ 代表一个边权 $w_v$。
• 如果 $P$ 中某叶子 $x$ 的最近服务器在子树 $v$ 外部，则 $x$ 的延迟至少为 $w_v$。
• 可以设计 DP：$dp[u][t]$ 表示子树 $u$ 内放 $t$ 个服务器，子树内 $P$ 点的最小总延迟，其中延迟计算要考虑跨过 $u$ 的边的贡献。

---

12. 具体 DP 定义（最终解法）

定义 KRT 的每个节点 $u$ 代表一个连通块，权值 $val[u]$ 表示合并时的边权（叶子节点 $val=0$）。

对于叶子节点（原图顶点）：

• 如果它是 $P$ 中的点，它需要被覆盖；如果不是，它不需要。

设 $f[u][t]$ 表示在子树 $u$ 中放置 $t$ 个服务器，且子树内所有 $P$ 中顶点都被覆盖时，这些顶点的最小总延迟（延迟计算只考虑子树内部的路径，跨过 $u$ 的边的延迟会在父节点处理）。

初始化叶子 $u$：

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

转移（合并两个孩子 $l$ 和 $r$ 到 $u$）：

• 我们枚举左子树放 $x$ 个服务器，右子树放 $y$ 个，总 $t = x + y$。
• 如果 $u$ 是内部节点（对应一条边权 $w$），那么左右子树的 $P$ 点如果被另一子树的服务器覆盖，则路径必须经过 $u$，那么这些点的延迟至少为 $w$。
• 因此，我们需要额外记录：是否左右子树有服务器。如果没有跨子树覆盖，就不加 $w$；如果有跨子树覆盖，就要加 $w \times$ (被跨子树覆盖的 $P$ 点数)。

更简洁的常见实现是：

• 对每个 $u$，计算 $cnt[u]$ = 子树内 $P$ 点数。
• 合并时，考虑跨过 $u$ 的边的贡献：
  如果左子树没放服务器且右子树有 $P$ 点，那么右子树的 $P$ 点会被左子树的服务器覆盖吗？不行，因为左子树没服务器。
  实际上，我们需要知道每个子树是否至少有一个服务器。

因此状态改为：$dp[u][t][0/1]$ 表示子树 $u$ 内放 $t$ 个服务器，且 $u$ 的连通块内是否有服务器，的最小总延迟。

---

13. 最终算法步骤

1. 建原图 MST。
2. 建 Kruskal 重构树（$2n-1$ 个节点）。
3. 树形 DP：
   • 叶子：$dp[u][0][0] = 0$（如果 $u \notin P$），$dp[u][1][1] = 0$（如果 $u \in P$ 或 $u \notin P$ 但放服务器），但注意 $u \notin P$ 时放服务器无意义但可行。
   • 内部节点 $u$ 合并左右孩子 $l,r$，边权 $w = val[u]$。
   • 转移时枚举 $l$ 的服务器数 $a$ 和 $r$ 的 $b$，以及 $l$ 是否有服务器 $f1$，$r$ 是否有服务器 $f2$。
   • 总服务器数 $t = a + b$。
   • 总延迟 = $dp[l][a][f1] + dp[r][b][f2] + w \times$ (跨子树覆盖的 $P$ 点数)。
   • 跨子树覆盖的点数 = 如果 $f1=0$ 且 $f2=1$，则 $r$ 的 $P$ 点被 $u$ 外覆盖，要加 $cnt[r]$；如果 $f1=1$ 且 $f2=0$，则加 $cnt[l]$；如果都有服务器，则不加（因为两边内部覆盖）；如果都没有，则 $u$ 的父节点会处理。
4. 最后，根节点 $root$ 的 $dp[root][k][1]$ 就是答案（根必须有服务器，否则无法覆盖整棵树）。
5. 对 $k=1..n$ 输出最小值。

复杂度 $O(n^2)$，因为合并时枚举 $a,b$ 总次数为 $O(n^2)$（树形背包）。

---

14. 时间复杂度

• 建 MST：$O(m \log m)$
• 建 KRT：$O(n \log n)$
• DP：$O(n^2)$，满足 $n \le 400$。

---

这样我们就得到了一个完整、可实现的解法。