题解 P8260【[CTS2022] 燃烧的呐球】

· · 题解

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

更好的阅读体验

题意

给定一棵树，定义 F(x,y) 为 x 子树与 y 子树异或的大小。给定若干个二元组 (x_i,y_i)，生成一张完全图，其中二元组 a 与二元组 b 之间的边权为 F(x_a,x_b)+F(y_a,y_b)，求最小生成树边权和。

## 分析 考虑 Boruvka，那么问题转化为加入二元组，查询异色最小边。 注意异色这个限制比较麻烦，先把它转换掉，我们可以直接维护贡献最小的位置以及与这个位置异色的贡献最小位置。 可以发现 $(x_a,x_b)$ 与 $(y_a,y_b)$ 只要有一对没有祖先关系，都很容易处理，枚举另一个，然后随便算算贡献就好了。（可以发现均有祖先关系这样算一定不优，不会影响答案） 接下来处理均有祖先关系的情况： - 目前点两维都是祖先：线段树合并维护一下； - 目前点存在一维是后代：动态维护一下 $x$ 维到祖先的链，然后再用线段树查自己为祖先时子树区间的答案，全局平衡二叉树查自己为后代时到根的链的答案； 可以发现复杂度均为 $O(m\log n)$，整体复杂度为 $O(m\log m\log n)$。 ## 代码 咕了，有时间写。