这次不是什么级数求和了。
对于一个有根树，我们如下定义重链剖分：
对于每个点 \(a\)，找到子节点中子树大小最大的那一个（如果有多个任取一个），记为 \(b\)，然后将 \((a, b)\) 这条边设为重边。
不难发现重边会形成若干条链，称为重链。每个重链中离根最近的点称为重链顶。
接下来我们如下定义一次重链收缩：
重链剖分之后从下到上考虑每个点，若这个点向父节点的连边是重边，就删除这个点。
若连边不是重边，记为 \((a, b)\)，就将 \(b\) 的父节点改为 \(a\) 所在重链的重链顶。
其实就是把所有重链顶都拿出来，保留祖先后关系建一个新的树。剩下的点都扔了。
不难发现一次重链收缩之后树的深度会变成 \(O(\log n)\)。
接下来我们要证明：进行 \(B>1\) 次重链收缩之后树的深度是 \(O(\frac{\log n}{\log B})\)，并且可以给出一个卡满的构造。
首先看上界证明。
考虑对于一个节点 \(a\) 和这个点的子节点 \(b\)，不妨假设 \((a, b)\) 是重边。
那么不难发现在进行一次重链收缩之后 \(a\) 的其他子节点仍然不变，\(b\) 会被拆成若干小子树，且每个大小都不超过 \(\frac{size(b)}{2}\)。
因此我们可以考虑将所有子节点子树按照 \(rnk(b) = \log size(b)\) 分组，每次我们会选 \(rnk\) 最大的子树，然后拆成一系列小的，大小和不超过 \(size(b)\) 且 \(rnk\) 不超过 \(rnk(b) - 1\)。
考察当我们枚举到 \(rnk = r\) 的子树的时候，由于总大小不会超过 \(size(a)\)，所以数量不会超过 \(\frac{size(a)}{2^r}\)。
因此进行 \(B\) 轮操作之后我们可以保证最大的 \(rnk\) 不超过 \(\log size(a) - \log B\)。
也即，最后每个节点 \(a\) 的子节点子树大小都不会超过 \(\frac{size(a)}{B}\)。
那么自然树的深度不超过 \(\frac{\log n}{\log B}\)。
然后是构造。
考虑构建一个满 \(B+1\) 叉树即可。
那么对于每个非叶子，至少会存在一个子节点，使得这 \(B\) 次重链收缩都没有影响这两个点之间的边。
我们可以将其称为原始边。
所以从根一路走原始边一定可以走到叶子。并且这条链在这 \(B\) 次操作里面没有被动过。
所以深度和最初的树是一样的。
我们知道满 \(B\) 叉树深度是 \(\Theta(\frac{\log n}{\log B})\)，所以就卡满了。
不难发现这个构造实际上适用于各种剖分方式。
也就是说无论以什么样的策略进行剖分，进行 \(B\) 轮之后的深度并不低于 \(\Omega(\frac{\log n}{\log B})\)。
所以目前来看多次剖分什么的前途不是很大。
挂一个 contribute
