树链剖分

概念

树链剖分是一种将树分割成若干条链的形式，以维护树上路径的信息的方式。

树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作 实链剖分），大多数情况下（没有特别说明时），树链剖分 都指 重链剖分。

重链剖分可以将树上的任意一条路径划分成不超过 $\log n$ 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。

版权声明

版权归属作者所有，可以任意转载，但需注明来源，侵权必究。

公告栏

博客创建不久，文章较少，作者在学业的空余时间完善博客。

正在进行的项目：

• HTML 参考手册
• OI 系列教程
• 博客的搜索功能（目前不可用）

HTML 参考手册

参考资料：绿叶学习网 Javascript中文网

缩点

模板题：P3387【模板】缩点

算法介绍

概念

缩点（Contraction of Strongly Connected Components）是图论中对有向图进行简化的重要操作，其核心是将图中的强连通分量（SCC）合并为单个节点。

gmail

nonsensitivitmvedgers@gmail.com

QQ

3971278103