@[command_block](/space/show?uid=58705)
卡子树大小确实是$O(n^2)$的,哪里$O(n^3)$了。
by Cqdnse @ 2019-01-17 17:29:53
你学下树上背包就知道了
by Cqdnse @ 2019-01-17 17:30:38
任意两点只会在$lca$处贡献一次复杂度
by Cqdnse @ 2019-01-17 17:30:59
上网搜了,没有一个解释复杂度的……
by command_block @ 2019-01-17 17:31:29
@[command_block](/space/show?uid=58705) 你枚举两个子树的大小，相当于枚举两个子树的点，然后你会发现，任意两点只会在他们的$lca$处被枚举到一次，所以复杂度是$O(n^2)$
by Cqdnse @ 2019-01-17 17:33:39
有道理哦!!!
by command_block @ 2019-01-17 17:34:22
我太菜了&&谢谢大佬
by command_block @ 2019-01-17 17:34:38
结贴,溜了。
by command_block @ 2019-01-17 17:35:01