树链剖分 学习笔记()

apple365:这个东西没有不可替代的作用

重链剖分

按照重儿子和轻儿子划分。
第一遍 求出 。
第二遍打 。
每次走重儿子会走出一条重链。之后再轻链里面走重儿子又可以把整棵树划分成若干条链。
性质：

dfs
siz[],fa[],dep[],son[]
dfn
  • 每一条链都是轻儿子开始，然后都是重儿子。
  • 每一条链的 DFS 序是连续的。
  • 每一颗子树的 DFS 序是连续的。

应用：

  • 求 LCA(x,y):
  • 检查 \(x\) 和 \(y\) 是否在同一条链上。若是，深度小的是 LCA。若不是，每次跳 dep[top[cur]] 更大的。
  • 求两点之间路径长度。
  • 将链或者子树转化成区间+数据结构。

长链剖分：

对于一颗树，将节点按照子树内的深度剖分，把深度最深的子树对应的子节点视为重儿子。
一条长链：由顶端点（轻儿子）+若干重儿子构成。
性质：

  • 一条长链的末端点一定是所在子树深度最大的节点。
  • 树上节点 cur 的 \(k\) 级祖先（\(k\) 从 \(0\) 开始）所在长链的长度一定大于 \(k\)。
  • 树上任意节点 cur 到根节点经过的轻边数不超过 \(\sqrt n\)。
————————

apple365:这个东西没有不可替代的作用

重链剖分

按照重儿子和轻儿子划分。
第一遍 求出 。
第二遍打 。
每次走重儿子会走出一条重链。之后再轻链里面走重儿子又可以把整棵树划分成若干条链。
性质：

dfs
siz[],fa[],dep[],son[]
dfn
  • 每一条链都是轻儿子开始，然后都是重儿子。
  • 每一条链的 DFS 序是连续的。
  • 每一颗子树的 DFS 序是连续的。

应用：

  • 求 LCA(x,y):
  • 检查 \(x\) 和 \(y\) 是否在同一条链上。若是，深度小的是 LCA。若不是，每次跳 dep[top[cur]] 更大的。
  • 求两点之间路径长度。
  • 将链或者子树转化成区间+数据结构。

长链剖分：

对于一颗树，将节点按照子树内的深度剖分，把深度最深的子树对应的子节点视为重儿子。
一条长链：由顶端点（轻儿子）+若干重儿子构成。
性质：

  • 一条长链的末端点一定是所在子树深度最大的节点。
  • 树上节点 cur 的 \(k\) 级祖先（\(k\) 从 \(0\) 开始）所在长链的长度一定大于 \(k\)。
  • 树上任意节点 cur 到根节点经过的轻边数不超过 \(\sqrt n\)。