题解：P13342 [EGOI 2025] 风力涡轮机

· · 题解

这是 官方题解 的 AI 翻译。

EGOI 2025 官方题解 - Wind Turbines (风力发电机)

任务作者：Chur Zhe Yaw, Shi Wei Tia

2025 年 7 月 16 日

引言

在这个问题中，我们给定一个无向带权图，需要回答一些查询，每个查询询问将图中每个节点连接到区间 [l_i, r_i] 内任意一个节点的最小代价。

子任务 1: M = N - 1 且 v_i = u_i + 1

在这个子任务中，图是一条路径。对于一个查询 [l_i, r_i]，最优解是添加所有边 (0, 1), (1, 2), \dots, (l_i-1, l_i) 和 (r_i, r_{i+1}), \dots, (N-2, N-1)。为了高效地为每个查询计算这个代价，我们可以使用前缀和进行预计算。运行时间是 O(N + Q)。

子任务 2: N, M, Q \le 2,000 且 \sum(r_i - l_i + 1) \le 2,000

在这个子任务中，约束足够小，可以为每个查询运行一个最小生成树 (MST) 算法，如 Kruskal 或 Prim。为了处理一些节点免费连接到岸边这一事实，我们需要在运行 MST 算法之前，添加一条连接 [l_i, r_i] 中所有节点的、边权为 0 的路径。这个解法的时间复杂度是 O(Q \cdot M \log M + \sum(r_i - l_i + 1))。

子任务 3: r_i = l_i + 1

在这个子任务中，每个查询都恰好有两个节点连接到岸边。这意味着，与求整个图的 MST 相比，每个查询都可以省去一条边的代价。应该被移除的边是路径上从 l_i 到 r_i 的最重的那条边。为了高效地为每个查询找到这条边，我们可以使用倍增 (binary lifting)：

首先，任意选择一个根，将图变为树。然后对于每个节点 v 和每个 2 的幂次 p，计算从节点 v 向上走 p 步的路径上遇到的最重边的权重。同时，也记录下从 v 向上走 p 步后到达的节点。这两个值都可以用动态规划在 O(N \log N) 的时间内计算出来。

然后，为了回答一个查询 (l_i, r_i)，我们可以计算从 l_i 到最低公共祖先 (LCA) 以及从 r_i 到 LCA 的路径上的最重边：我们可以像标准的倍增 LCA 算法那样“向上走”到 LCA，并取沿途找到的最重边的最大值。运行时间是 O(N \log N + Q \log N)。

子任务 4: 1 < c_i \le 2

这个子任务可以用与 100 分解法（见下文）类似的观察来解决，但有显著的简化。特别地，根据区间 [l, r] 的大小，我们知道总共需要支付多少条连接的费用。因此，我们只需要找出需要使用多少条代价为 2 的连接。这也可以通过计算在每个查询中，只由 c=1 的边组成的图中有多少个连通分量来得出。

子任务 5: \sum(r_i - l_i + 1) \le 400,000

假设 q_i = [l_i, r_i] 是一个查询。这个查询的代价是原始图的 MST 代价减去某些边的代价。具体来说，那些在 MST 中连接了两个集合，而这两个集合都包含来自 [l_i, r_i] 的风力发电机的边，正是我们在 MST 中不需要支付费用的边。为了解决这个查询，我们只需要找到这些边的代价之和。

我们使用 Kruskal 算法来构造输入图的 MST。我们可以稍微扩展 Kruskal 算法中使用的并查集数据结构来计算 MST。在此之前，我们读入所有查询，并在每个节点上存储一个它所属的查询列表。由于 \sum(r_i - l_i + 1) \le 400,000，我们不会存储太多的值。当合并两个集合时，我们也可以合并它们的查询索引列表，并存储在合并后的集合中。我们通过遍历较小集合中存储的所有查询索引来做到这一点，并：(1) 检查它们是否也存储在较大的集合中（如果是，我们可以记录此信息并更新该查询的成本节省），以及 (2) 将它们添加到较大集合的列表中。总的来说，这需要 O(N \log N) 的时间，因为每当一个顶点作为较小集合的一部分被处理时，它在联合操作后将属于一个至少是原来两倍大的集合。

替代解法：也可以使用虚树 (Virtual Trees) 在 O((r_i - l_i + 1) \log n) 的时间内处理每个查询 (参见例如 https://codeforces.com/blog/entry/140066)。

子任务 6: l_i = 0

有多种方法可以完成这个子任务：

我们把细节留给读者去探索 :)

完整解法

要获得此问题的满分，我们需要一些思路和数据结构。

预处理：让我们在处理任何查询之前，先对输入图运行 Kruskal 的 MST 算法。在这样做的时候，我们可以构建一棵包含 2n-1 个节点的 Kruskal 树，其中包括：

构建这棵树的步骤如下：

  1. 按成本非递减的顺序对所有电缆进行排序。
  2. 按顺序处理每条电缆：
    • 如果 u_i 和 v_i 已经连接，跳过这条电缆。
    • 否则，创建一个新的内部节点 y 并使其成为 u_i 和 v_i 所在树的根的父节点。
    • 然后，将 u_i 和 v_i 所在树的根更新为 y。

可以观察到，任何不在原始 MST 中的电缆在任何情况下都不会被建造；因此我们可以安全地忽略这些电缆。 现在，让 y_i 是树中对应于电缆 i 的节点。它当且仅当 y_i 至少有一个直接子节点，且该子节点的子树中所有叶子节点都没有发电厂时，才会被建造。换句话说，电缆 i 不被建造，当且仅当 y_i 的两个直接子节点在它们各自的子树中都至少有一个发电厂。

我们还将预处理这棵 Kruskal 树，以便我们可以在 O(\log n) 或 O(1) 的时间内回答 LCA 查询。

处理查询：我们按 r_i 的递增顺序处理查询（扫描线）。如果 Kruskal 树中的一个（叶）节点的索引小于我们当前正在处理的 r_i，我们就称它为激活 (active) 的。

考虑 Kruskal 树中的一个内部节点 u，让 k_u 是以 u 为根的子树中任何激活叶子的最大索引（这最多是 r_i）。另外，假设 a 和 b 是 u 的直接子节点。那么，对应于 u 的电缆不被建造，当且仅当 k_a \ge l_i 和 k_b \ge l_i。确实，这仅在以 a 为根的子树和以 b 为根的子树都包含在 [l_i, r_i] 范围内的风力发电机时发生。

我们现在注意到：

k_u = \max(k_{u.a}, k_{u.b})

因此，我们需要高效地计算满足上述条件的电缆的 c 值之和。关键的观察是，这个和等于以下各项的和：

在这里，u 可以是一个内部节点或一个叶节点。u.par 表示节点 u 的父节点（如果节点 u 没有父节点，定义 w_{u.par} = 0）。如果 u 是一个内部节点，w_u 是对应于 u 的电缆的成本。如果 u 是一个叶节点，定义 w_u = 0。

为此，我们将维护一个以 k_u 为索引的树状数组（或线段树）来高效地计算这个和。具体来说，对于每个 l，我们将维护所有满足 k_u \ge l 的 u 的 w_{u.par} - w_u 之和。

我们可以在执行扫描线的同时有效地维护 k_u 的值。当激活一个叶子 x 时，从该叶子到根的所有节点的 k 值都将被设置为新激活叶子的索引。沿着这条从叶到根的路径，有几个共享相同 k 值的“链 (chains)”。

我们将一条链定义为从某个内部节点 u 到叶子 k_u 的最长路径。我们称这条链上最顶端的顶点为链的根。

当激活一个叶节点 x 时（当前最大的激活节点），这将创建一条从树根一直到 x 的新链，并覆盖这条路径上的任何先前存在的链，使它们变短。

我们可以观察到，在对 r 的扫描线过程中，链改变根的总次数是 O(N \log N)。这是因为，在具有两个大小为 s_1 和 s_2 的子树的节点 u 处，穿过 u 的链最多可以改变方向 \min(s_1, s_2) 次。最坏的情况是在一个平衡二叉树中，根处的链改变方向 N/2 次；根下一层的节点处的链改变方向 N/4 次，依此类推。

根据上述观察，我们可以逐一处理每个链根的变化（总共 O(N \log N) 次），并且每次发生变化时，在 O(\log N) 的时间内更新树状数组中受影响的索引。

这些链可以通过简单地存储所有链根的 k_u 值来维护，然后在激活后使用 LCA 查询向下遍历新的根到叶路径。确实，假设我们激活了节点 x，那么我们可以通过查询 x 和 k_u 的 LCA 来找到根到 x 路径与从 u 开始的链的交集上的最后一个重叠顶点。（或者，树链剖分或其他树数据结构可以帮助遍历这些路径）。然后我们可以继续到这个 LCA 的一个子节点，处理下一条链，同时更新树状数组和链根。

时间复杂度：排序边需要 O(M \log M)，树状数组查询需要 O(Q \log N)，激活叶子并更新树状数组需要 O(N \log^2 N)。