kruskal 重构树 课件

· · 算法·理论

校内讲课用。配套题单。
校内题单所以你理论上看不到，没关系反正题单里的题下面都会给出来。
转存到自己的团队里公开了。话说 kkk 把个人题单数量上限卡死是有什么心事吗，是不是等着卖会员啊。那你快把会员上线啊我要交 rmj /fad

因为作者水平很差，在题库里面跟着标签找题发现有的题好难啊根本把会，所以这篇文章肯定有不准确的地方 /kel

Gist

:::info[因为这个东西太简单了所以你完全可以收起我胡的一堆废话直接去爆切例题 /kel]{open} 默认大家会 kruskal。

先说这个东西能干啥。可以解决很多瓶颈路相关问题，把这些东西转化成树上问题从而得到更快更简单的做法。

时空复杂度啥的看这个树上问题的复杂度，树的形态比较特殊所以有很多性质可以利用。

然后，这个东西其实我怀疑大家其实都研究过，我声称这是发明和学习难度最低的数据结构。所以先大概讲一下这个东西是怎么构建，以及有什么性质。

如何建一个连通图的 kruskal 重构树：

建完了。注意重构树除了叶子都是虚点。

有什么性质呢？假设我们的 kruskal 做的是最小生成树。

存在一个从 u 到 v 最小化最大边权的路径，这个最大边权的边是 u,v 在这个树上的 \text{LCA} 所代表的边。

另外根链上边权有单调性。这个显然。

其他没了。不过很有用。

关于第一点，这个正确性的话，考虑到瓶颈路只考虑 kruskal 出来的生成树是不劣的，于是变成树上路径的最值。然后再考虑 kruskal 的正确性，\text{LCA} 就是将两个点连通的最大边权，于是就是对的。

后面的题目太简单前面的介绍太水致歉 /kel

因为华语水平太差所以，简要题意就不给了。

Examples

P1967 [NOIP 2013 提高组] 货车运输

:::success[sol] 对着最大生成树建 kruskal 重构树，每次询问就是求个 \text{LCA}，复杂度 O(n\log n+q)。 :::

P4768 [NOI2018] 归程

:::success[sol] 第一步可以免费走到瓶颈路不超过定值的所有点，于是就是重构树上一个子树内的所有点都可以免费走到。这个点倍增跳父亲就可以找到。

从 1 向外对每个点跑最短路，把路径长度作为权值打到叶子上，忽略掉虚点的权，维护子树 \text{min} 即可。

复杂度 O(n\log n)。

P4197 [ONTAK2010] Peaks 加强版

:::success[sol] 和上一题一样倍增找到对应祖先，问题变成子树第 k 大，拍扁变成序列第 k 大，主席树即可。这个同时也是 QTREE3，为啥这个是紫来着。

复杂度 O(n\log n)。显然是在线的。

P4899 [IOI 2018] werewolf 狼人

:::success[sol] 边没有权了，但是我们可以套路的赋权。分别对人和狼都建树。

考虑到对于人一个边能走当且仅当两个端点都不小于 L，狼则是都不大于 R。

于是前者我们令端点 \min 为边权，后者则是 \max。建树。

每次查询倍增后变成求子树交，dsu on tree 即可，不会的请看这个。

维护排名不一定 pbds，考虑到值域是 O(n) 并且没有重复元素，也可以直接上 BIT 就是了。

总体复杂度 O(n\log^2 n)。

P13084 [NOISG 2017] I want to be the very best too! / 宝可梦大师

:::success[sol] 和上一题一样的建边，建树。

带修子树数颜色，压扁变成板子带修莫队。

复杂度 OTn53。

P5168 xtq玩魔塔

:::success[sol] 比上一题要多维护一个 \text{LCA}。 :::

P13548 [OOI 2022] Air Reform

因为比较诈骗所以给些 Hint /fad

:::warning[Hint1] 停止思考减少无效边跑 kruskal 的做法，应该没啥前途。

利用一些已有的偏序关系去思考用什么方法枚举比较少的东西，以此来完成 kruskal 要做的事情。

:::warning[Hint2] 不妨再看看你扔掉的暴力。

这个题没那么难，是简单题来着。不要过度思考。

::::success[sol]

读题是不是十级算法，好难啊。我怎么又花了一万年读题。

首先对原图建最小生成树的重构树。

加边补成完全图，新边边权是两个点在原树上 \text{LCA} 的权值。

然后只保留加的边，建最小生成树的重构树，把原图的所有边当成查询，问这些点对的 \text{LCA} 的权值。

难点在于不要被吓住。

第二个树边太多直接建建不出来，考虑换一个方法枚举边。

因为重构树点权自上向下有单调性，于是可以直接自底向上合并。

优先考虑暴力，直接对每个点维护子树内所有的连通块以及内部点。

显然对于每个点，左子树的连通块和右子树的连通块在这里合并起来是最优的。

我们直接暴力枚举左侧每个连通块的每个点和右侧每个连通块的每个点，判断能不能合并，能就合并起来。不能合并当且仅当原图中两个点有边。

这个是对的。

:::info[为什么是对的？请先自己思考] 合并 O(n) 次。

无法合并最多 O(m) 次。
时间复杂度 O(n\log n)。

P5311 [Ynoi2011] 成都七中

:::success[sol] 类似狼人的变成两个重构树子树交颜色数的形式。

难点在于如何维护子树交的颜色种类数。这个很难啊！

子树交依旧 dsu on tree，另一个压扁成序列，于是变成带修区间颜色数，不太行，扔掉。依赖一下树的性质，我们做带修子树颜色数。

考虑刻画每个颜色的贡献，显然每个点的根链全部都是能吃到这个颜色贡献的，但不能重复吃。

考虑到，我们每次修改都在当前点修改的同时找到第一个不被影响的祖先也进行修改即可。这个点一定是当前修改点在 dfn 序上的前驱或者后继与当前点的 \text{LCA}。

于是维护一个 dfn，再维护一个根链加单点查就可以了。使用 zjh trick 可以随意使用 BIT 维护，复杂度 O(n\log^2 n)。

Practice

未来可能会加题，例题部分到此为止了。

留一些习题。
大家会做了以后一定要记得教会我 /kel

事实上本节课标题是重构树 & 次小生成树，所以这里也有个后者的题单。