剖

· · 算法·理论

众所周知，长剖的轻子树高度和是 O(n)，然而点到根可能有 O(\sqrt n) 条轻边。

众所周知，重剖点到根有 O(\log n) 条轻边。然而不那么众所周知的，轻子树的高度和可以是 \Omega(n\log \log n)。这个下界同时是紧的。可以参考赵海鲲同学的集训队论文。

有没有一种剖分方法同时满足轻子树高度和是 O(n)、每个点到根只有 O(\log n) 条轻边呢？

:::success[有的兄弟有的] 若长子树的深度大于次长子树的深度的两倍，则选择长儿子为实儿子；否则选择重儿子为实儿子即可。 :::