当前位置: 首页 > news >正文

Kruskal 重构树

Kruskal 重构树是在无向图做最小生成树的 Kruskal 算法时可以同时构建出来的一棵树。

性质

事实上,这里的“重构”是针对原图的最小生成树而言的。
Kruskal 重构树用非叶子节点表示原图的最小生成树上的边,点权即为原图上的边权,用叶子节点对应原图中的节点,故 Kruskal 重构树节点数是 \(2n-1\)。(不要忘记开 \(2\) 倍空间)
由于一条边连接两个节点,故 Kruskal 重构树一定是一棵二叉树。

构建过程

我们在 Kruskal 算法过程中,若选定一条边作为图上的最小生成树边,就创建一个新节点代表这条边,左右儿子是这条边所连两个连通块的根节点。
也就是说,Kruskal 重构树的构建过程就是将 \(n\) 个散点通过添加 \(n-1\) 个公共祖先构建出来的,由于我们是在 Kruskal 算法过程中跑出来的,所以先加入的点(即深度较大的点)点权较小(事实上可以理解成是一个大根堆),同时可以得出一个性质:定义原图上两点间的距离为两点间路径的边权最大值,则原图中两点间距离的最小值就是 Kruskal 重构树上两点 LCA 点权
若原图不连通,建出的就是 Kruskal 重构树森林。

例题

星际导航

板题,建出 Kruskal 重构树后直接查 LCA 即可。

[ONTAK2010] Peaks 加强版

从一点 \(u\) 开始只经过权值小于等于某个值 \(x\) 的边,相当于可以到达 Kruskal 重构树中包含 \(u\) 的、以权值小于等于 \(x\) 的节点为根的子树的所有叶子节点。可以直接倍增找到该子树的根。查询第 \(k\) 大可以直接拍到 dfs 序上用主席树做。

[NOI2018] 归程

我们以海拔为关键字降序排序,建出的 Kruskal 重构树满足:若水位线低于根节点权值,则子树内叶子节点在原图上相互可达。则此时花费为子树内所有叶子节点到达 \(1\) 号点距离的最小值。这个可以最短路预处理,建树时倍增维护到非叶子节点上。

http://www.hskmm.com/?act=detail&tid=30942

相关文章:

  • 解决Win11 24H2 缺少Microsoft Print to PDF组件,重新添加出现0x800f0922错误的问题
  • “顾客需求必响应”!国标GB28181算法算力平台EasyGBS国标协议报警预案怎么弄?4步实操指南来了
  • 机器视觉双雄YOLO 和 OpenCV 到底有啥区别?别再傻傻分不清!
  • 基于定制开发开源AI智能名片S2B2C商城小应用的文案信息传达策略研究
  • AI工具学习02 - 使用 ChatGPT 进行 PRD 产品设计
  • mysql默认事务隔离级别,从入门到精通的完全指南
  • 11111111111
  • 利用 OpenTelemetry 集成 JMX 监控
  • Java 23种设计模式的详细解析
  • 基于Golang+Gin+Gorm+Vue3母婴商城项目实战
  • 2025 年无缝钢管厂家推荐排行榜, SA333Gr.6 /SA106B/SA106C/A106B/SA210C/ 25MnG/SA53B/A53B /L245NS/P22 无缝钢管厂家推荐
  • 英语_阅读_telescope_待读
  • fiddler早期免费版下载,fiddler抓包工具及使用
  • 零点城市社交电商卡密串码插件:全场景虚拟商品运营解决方案
  • 完整教程:Nginx 核心功能配置:访问控制、用户认证、HTTPS 与 URL 重写等
  • 宝塔计划任务root能正常运行,www用户不能按时运行
  • 介绍 Qodo(原 Codium):新名字,不变的质量承诺 - 公众号
  • mas激活工具安装教程!专业版激活工具!!Microsoft Activation Scripts v3.6 MAS中文汉化版(激活工具)
  • 英语_阅读_Lunar exploration_待读
  • 中文语音识别不建议使用VOSK
  • 213123123123123
  • 时序数据库 IoTDB 集成 DataGrip,支撑跨模态多库融合管理
  • Sql Server安装报错“服务没有及时响应启动或控制请求”
  • 题解:CF1830E Bully Sort
  • 斑马日记2025.10.10
  • 斑马日记2025.10.12
  • Androidify:基于Gemini AI的安卓机器人定制应用
  • 入门指南:使用 Playwright MCP Server 为你的 AI Agent 赋予浏览器自动化能力
  • 实战教程:构建能交互网页的 AI 助手——基于 Playwright MCP 的完整项目
  • popcount 题