最短路算法流程

1. Floyd（$O(n^3)$，多源最短路径）

浅谈 LCA

作者：Gemini 2.5 flash

---

简介

在图论中，最近公共祖先（LCA） 是指在一棵树中，距离两个给定节点最近的公共祖先节点。寻找LCA是树结构算法中的一个经典问题，在很多应用中都有重要作用，比如在计算基因序列的相似性、文件系统路径查找等方面。

1. 朴素算法

实现思路

朴素算法通常指的是最直观、最简单的暴力解法。对于LCA问题，一种朴素的思路是：

1. 提升深度一致：将两个节点中深度较大的节点向上移动，直到它们与深度较小的节点处于同一深度。
2. 同时上移：两个节点再同时向上移动，直到它们相遇。相遇的节点就是它们的LCA。

三维偏序（bitset 做法）

模板题目链接 洛谷文章链接

树链剖分

概念

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

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

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

缩点

模板题：P3387【模板】缩点

算法介绍

概念

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