瞎扯:我觉得这个部分的图论挺有意思的所以多写了一点XD 树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。

具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

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

CA(Lowest Common Ancestor) cover: icon: editLink: false order: 4 author: badb0ttle date: 2025-8-26 category:

• 算法 tag:
• 图论

此页面会在文章列表置顶

sticky: false star: false footer: 图论

---

LCA

原文oi wiki:最近公共祖先 两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 为了方便，我们记某点集 S=$\{v_1,v_2,\ldots,v_n\}$ 的最近公共祖先为 $\text{LCA}(v_1,v_2,\ldots,v_n)$ 或 $\text{LCA}(S)$。 特殊性质:LCA(l,l+1,l+2,...,r)=LCA(dfs序最小,dfs最大)