子树大小剪枝是对的啊，你应该搞错了
by 142857cs @ 2019-01-17 16:46:42
N^3怎么想的啊
by Dark_Forest @ 2019-01-17 16:51:37
@[command_block](/space/show?uid=58705) 双重扫把图只能卡一次合并的复杂度为$O(N^2)$，对于整体而言复杂度还是没有问题的。。最卡也只能是完全二叉树，但是只能卡到$O(N^2logN)$
by CYJian @ 2019-01-17 17:05:13
@[暮雪﹃紛紛](/space/show?uid=20782)
您再冷静分析一下复杂度
by shadowice1984 @ 2019-01-17 17:11:31
不是$O(n^2)$吗
by Cqdnse @ 2019-01-17 17:12:47
任意两点只会在$lca$处贡献1的复杂度
by Cqdnse @ 2019-01-17 17:17:13
~~挠头~~
我又naive了?
大家能清楚点解释吗?
by command_block @ 2019-01-17 17:21:48
@[shadowice1984](/space/show?uid=56384) 好吧是我算错了。。单次是$O(N^2)$，有$N/2$次合并，的确会炸。。
by CYJian @ 2019-01-17 17:25:21
可为什么O(n^3)跑3000跟飞一样?
by command_block @ 2019-01-17 17:28:44
@[Cqdnse](/space/show?uid=63348) 大佬来解释下。
by command_block @ 2019-01-17 17:29:02