外观
2026-03-05
令一棵树的根节点为 uuu,对于它的所有子节点记作 viv_ivi,可以取一个子树大小最大的 vmaxv_{max}vmax,将其称作重边,其他的边称作轻边,容易发现,很多重边会连在一起,成为重链。可以证明,一棵树中,最多有 logn\log nlogn 条重链(可以理解为每走一条重边就会减少至少 x2\frac{x}{2}2x 个节点)。 由于重边个数是 log\loglog 级别的,所以重链也是 log\loglog 级别的。
版权归属:lyrgo
许可证:署名 4.0 国际 (CC-BY-4.0)