树链剖分

简单回顾一下树链剖分(以下摘自2009年漆子超的论文《分治算法 在树的路径问题中的应用 》):

定义:

  • 将树中的边分为两类:轻边和重边。
  • 记\(Size(U)\)表示以\(U\)为根的子树的结点个数。
  • 令\(V\)为\(U\)的儿子中\(Size(V)\)最大的一个,那么我们称边\((U,V)\)为重边,其余边为轻边。
  • 我们称某条路径为重路径,当且仅当它全部由重边组成。

性质:

  • 性质1:如果\((U,V)\)为轻边,则\(Size(V) \leq \frac{Size(U)}{2}\)。
  • 性质2:从根到某一点的路径上轻边的个数不大于\(O(log_{2} N)\)。
  • 性质3:我们称某条路径为重路径,当且仅当它全部由重边组成。那
    么对于每个点到根的路径上都不超过 \(O(log_{2} N)\) 条轻边和
    \(O( log_{2} N)\)条重路径。

证明:

性质1根据定义来看比较显然。

性质2的话,从某点出发向上走,每经过一条轻边,当前子树的大小就至少变成2倍(由性质1得),所以根到某一点的路径上轻边的个数不大于\(O(log_{2} N)\)。

性质3,因为重路径是被轻边间隔开的,所以从每个点到根的路径上经过的重路径的条数是不超过轻边条数+1的,所以也是\(O( log_{2} N)\)级别的。

应用:

  • 用于求LCA(推荐)
  • 与线段树结合维护查询树链信息
  • 利用重链dfs序连续,代替倍增求点x往上跳k步的点是谁。

代码:

\(deep\)数组表示深度。

\(fa\)数组表示父节点。

\(son\)数组表示重儿子。

\(top\)数组表示每个点所在重链的顶端节点。

\(pos\)数组表示每个点按照重链优先dfs下的dfs序。