我觉得toptree也能做？那为什么不叫模板toptree呢？
by Gemini7X @ 2020-08-20 12:05:01
@[zhy137036](/user/178294) 长链剖分的复杂度是不对的吧
对于一条轻边 $u \rightarrow v$ 而言，必须有 $\operatorname {len}(u) \ge \mathrm {len} (v) + 1$。也就是说，每从轻边往上跳一步，长链的长度就至少增加 1。所以最坏的情况下往上跳 $k$ 步的节点总数为：
$$n = 1 + 2 + 3 + \cdots + k = \dfrac {k (k + 1)} {2}$$
显然 $k = O(\sqrt {n})$，所以长剖的复杂度是 $O(n \sqrt {n})$。
所以复杂度不太对吧
by longlongzhu123 @ 2020-08-20 12:09:10
好像长剖在优化某些 DP 的时候能够保证复杂度正确？这个我也没有研究过。
by longlongzhu123 @ 2020-08-20 12:10:46
因为数据水
by Priori_Incantatem @ 2020-08-20 12:11:05
QWQ
by longlongzhu123 @ 2020-08-20 12:11:26
@[longlongzhu123](/user/57525) 谢谢，那就让管理员加强一下数据吧
by zhy137036 @ 2020-08-20 12:15:51
1e5 的 $n\sqrt n$ 叫我卡个锤子
by mrsrz @ 2020-08-20 12:21:09
srz！
by impuk @ 2020-08-20 12:21:53
srz!
by zhy137036 @ 2020-08-20 12:39:35
srz!
by _SkyBlue @ 2020-08-20 12:43:29