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

P8260 [CTS2022] 燃烧的呐球

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

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

一个简单一些的问题

给定一棵 $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))$。

正确性证明（感谢 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_1$

$G_2$ 和 $G_3$

$G_4$