# 长链剖分学习笔记

# 基本

​ 与重链剖分类似的，长链剖分将一棵树剖出若干条互不相交的链。

​ 但长链剖分中的重儿子不是子树大小最大的，而是深度最大的儿子（定义深度为一个点到其子树其他点经过点数中最大的一条），不妨将其称作长儿子。

​ 类比重链剖分，我们定义长边为一个节点与它的长儿子连成的边，若干长边连成一条长链，定义链顶为长链中深度最大的节点，链底为长链中深度最小的节点。

# 性质

• 一个点到其长链链底的路径，是这个点到其子树所有点的路径中最长的一条。（ $\color{gold}\texttt{显然}$ ）

• 一个点到根的路径，最多经过 $\sqrt n$ 条虚边。

  • 证明：一个点深度为 $k$ ，往上如果是虚边，那么上面点的子树大小最小要加上 $k+1$ ，设跳 $x$ 条虚边到根，树的大小最小为 $\frac{x(x+1)}{2} = n$ ，故 $x$ 大约为 $\sqrt n$ 。

• 每条长链长度之和是 $\mathrm O(n)$ 级别的

# 技巧

• 长剖优化与深度有关的 $dp$ .

有点类似 $\texttt{Dsu On Tree}$ ，大概是每次把当前 $dp$ 数组 $O(1)$ 继承给长儿子，这个可以用指针做。