震惊!传说中的暴力压标算!!!
by 传奇英雄 @ 2020-10-12 10:43:30
@[传奇英雄](/user/61602) 珂以证明这个做法是 $O(n^2)$ 的吧。
你拿毛毛虫,蒲公英,菊花图试一试,全都卡不掉
by Stinger @ 2021-03-16 10:42:44
@[传奇英雄](/user/61602) 题解有一篇谈到了树包时间的问题:
"
关于时间复杂度网上有一篇讲稿 十分不错,引用一段:
... 因为每次合并一棵子树时付出的代价是”已经合并的兄弟子树的大小之和”*”正在合并的这棵子树的大小”,实质上是树上每对节点在LCA处贡献时间复杂度 ...
所以是n^2
的。"
by Guxue @ 2021-03-23 18:54:35
如果你把siz[]在一开始dfs打表打出来,就是正经n^3,会T飞
by Guxue @ 2021-03-23 18:57:37