题解：P8260 [CTS2022] 燃烧的呐球

lichenghan · 2025-09-14 15:45:43 · 题解

P8260 [CTS2022] 燃烧的呐球

前言：Rainbow_qwq 老师在讨论区声称有单 \log 做法，但是并没有写题解，也并没有其他人写这个做法。 于是这是一篇时间复杂度做到 O(n+m\log n) 的题解。做法完全参考了 Rainbow_qwq 老师的代码（也有一些是实在看不懂自己口胡的），除了一些小细节外是一致的。但是由于作者比较菜，证明不出更改了小细节的自己的做法，下面的叙述将与 Rainbow_qwq 老师的解法一致。

一句话题解：寻找可能在最小生成树中被用到的 O(m\log n) 条边。

若无特殊说明，下文的“图”均指边带权的无向完全图。对于图 G 以及 G 的两个顶点 u,v，记 G(u,v) 表示 (u,v) 这条边的边权。

一个简单一些的问题

本文将基于这个问题的优秀解法进行优化。

给定一棵 n 个点的树，点 u 有权值 f_u,g_u（f_u,g_u \le O(n)）。构造图 G，若 u 为 v 的祖先则 G(u,v)=f_u+g_v，若 u,v 不呈祖先后代关系则 G(u,v)=+\infty。求这张图的最小生成树。

时间复杂度要求：O(n\alpha(n))。

为方便叙述，我们不妨设所有 f,g 互不相同。

解法：指定 1 号点为根，设点 u 的父亲是 p_u。对于每个不是根的点 u，我们求出 u 的祖先（包含自身）中 f 最小的点 F_u，求出 u 的子树（包含自身）中 g 最小的点 G_u。取边 (u,F_{p_u}),(p_u,G_u),(F_{p_u},G_u)。我们声称，只需要把上述取出的 3n 条边拿出来跑 Kruskal 就能拿到原图的最小生成树。

由于边权在 O(n)，Kruskal 中对边的排序可以使用桶排序在线性时间内完成，因此总复杂度是 O(n\alpha(n)) 的。

正确性证明（感谢 UOJ 群中的 thomaswmy 老师提供帮助）：

非常建议在看下面的文字的同时画图以便理解。

接下来将反复使用下面的事实：对于一条边 (u,v)，若存在一条路径使得路径上经过的所有边的权值都小于 (u,v) 的权值，则 (u,v) 必定不在最小生成树上。证明略。

对于一个不是根的点 u，考虑 G_u \ne u 的情况。此时，对于所有不等于 F_{p_u} 的 u 的祖先（不包括 u 自身）v，可以使用 u\to F_{p_u}\to G_u\to v 这条路径和前文的结论推导出 (u,v) 这条边不属于最小生成树。

同样的，如果 F_{p_u}\ne {p_u}，则对于 u 子树内所有不等于 G_u 的点 v 都有 (p_u,v) 不属于最小生成树。

现在考虑两个点 (u,v) 满足 u 是 v 的祖先，且 F_u=u,G_v=v。设 x 是 u 到 v 路径上第一个满足 F_x\ne u 的点；设 y 是 v 到 u 路径上第一个满足 G_y\ne v 的点。那么，路径上没有点 z 满足 F_z=u,G_z=v 当且仅当 x,y 均存在且 x 是 y 的祖先。此时有 f_x<f_u 且 y 子树中存在点 w 满足 g_w<g_v。考虑 u\to w\to x\to v 这条路径即可证明边 (u,v) 不在最小生成树上。

至此，每一条边要么被选中，要么被证明不属于最小生成树。

接下来正式进入本题的题解。

大体思路：设原图为 G。如果我们能找到若干张图 G_1,\cdots,G_k 使得 \forall u,\forall v,G(u,v)=\min\limits_{i=1}^kG_i(u,v)，并快速求出 G_1,\cdots,G_k 的最小生成树 T_1,\cdots,T_k，那么 T_1\cup\cdots\cup T_k 的最小生成树就是原图的最小生成树。

下面将逐步给出构造。

定义 siz(u) 为为原树上 u 的子树大小；

设原树上某边 (u,v) 的长度为 |siz(u)-siz(v)|，以此定义 dist(u,v) 为树上两点的距离；

定义 D_1(a,b)=siz(a)+siz(b)；

定义 D_2(a,b)=dist(a,b)；

定义 D_3(a,b)=\begin{cases}|siz(a)-siz(b)|,&a,b 互为祖先后代关系,\\+\infty,&\text{otherwise}.\end{cases}

容易发现 \min(D_1(a,b),D_2(a,b))=\min(D_1(a,b),D_3(a,b))=D(a,b)。

（证明提示：当 a,b 互为祖先后代关系时 D_1=D，否则 D_2=D_3 =D ）

构造四张图 G_1,G_2,G_3,G_4：

最简单的部分。此时 G_1((x_1,y_1),(x_2,y_2))=siz(x_1)+siz(y_1)+siz(x_2)+siz(y_2)，取 (x,y) 为 siz(x)+siz(y) 最小的点，应该能容易发现其最小生成树是以 (x,y) 这个点为中心的菊花。

G_2 和 G_3

由于这两张图是对称的，下文将以 G_3 为例。

回顾一下，G_3((x_1,y_1),(x_2,y_2)) 在 y_1,y_2 为祖先后代关系时权值为 siz(x_1)+siz(x_2)+|siz(y_1)-siz(y_2)|，否则为正无穷。

整理，设 f(x,y)=siz(x)+siz(y),g(x,y)=siz(x)-siz(y)。此时，G_2((x_1,y_1),(x_2,y_2)) 在 y_1 为 y_2 祖先时权值为 f(x_1,y_1)+g(x_2,y_2)。可以简单化归到前文提到的问题。

G_4

回顾一下，在 y_1 是 y_2 的祖先时，G_4((x_1,y_1),(x_2,y_2))=dis(x_1,x_2)+siz(y_1)-siz(y_2)。

对 x 跑点分治。考虑某个重心 g 周围的子问题，dis(x_1,x_2) 可以写成 dis(x_1,g)+dis(x_2,g)。

和上面一样，设 f(x,y)=dis(x,g)+siz(y),g(x,y)=dis(x,g)-siz(y) 即可化归到前文提到的问题。

于是最后把上面求出来的最小生成树拼起来跑 Kruskal 就好了，瓶颈在 G_4 中的点分治，复杂度是 O((n+m)\log n)。

注意我们其实并不需要在每次跑前文的简单问题是都跑 Kruskal，可以只把边选出来，最后再跑一次 Kruskal（否则复杂度上还要带 \alpha(n)）。

如果要做到 O(n+m\log n) 的话可以把有用的 2m 个点拉出来建一棵虚树。