kruskal重构树 快记录 最后更新于 2025-05-01 21:56:23

### 9. CF2021E2 - Digital Village (Hard Version) Kruskal重构树 看题解做出 古早时期，我曾经总结了以下处理方法： ``` 处理联通性：离线，排序，并查集 ``` 这个处理方法其实本质是Kruskal 事实上这个处理方法对于 一张图 $u$ 到 $v$ 路径上最大边的最小值。（即路径权值定义为边权max） 问题来说，可以更加一般化地 静态化地转化为Kruskal重构树 (Kruskal重构树之于Kruskal)类似于(点分树之于点分治)，其实是把一个动态的过程转化为一个静态的树的结构，使得在线处理的重复过程得以去除。 不同点在于点分树的核心在于深度O(logn)使得许多对子树的暴力操作可以实现，而Kruskal重构树则是把 路径权值问题 转化为 点权值的问题 进行处理。 对于这题来说 感觉图论的基础算法真不多，其实所有图论题都是转化为图论基础算法与扩展