lghjl

摘要： 一种不同于重链剖分的剖分方法，就是选子树里链最长的作为重儿子。性质1：长链总和为\(n\)。性质2:从一个节点到根节点的轻边个数不超过\(\sqrt{n}\)。原因，因为是长链，所以从轻边跳上去所在的长链的长度一定比现在这个大，\(1+2+3+4\dots\)，所以是\(\sqrt{n}\)个。 应 阅读全文