F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register |
---|
Problem 5165 >> 想知道一下这题std |
Rose_max @ 2018-04-09 08:48:43
据说由于数据太水我就卡过去了。。
想知道一下std是什么 |
EdwardFrog @ 2018-04-09 16:42:19
好像只要预处理不超过O(n),空间不超过O(n),单次询问不超过O(logn)都能过
没放时限的时候一个树剖日过去了 |
ruanxingzhi @ 2018-05-12 18:37:27
bz上的数据不是我造的(不过当时胡策的时候我造的数据也水QAQ)
标程是用Tarjan,总共O(n alpha(n))。 用到一个结论:树上多个点的LCA,就是DFS序最小的和DFS序最大的这两个点的LCA。 此结论的证明: https://www.zhihu.com/question/46440863/answer/165741734 |
kczno1 @ 2018-05-16 15:45:22
询问不超过1000次话,用O(n)-O(log)求lca,复杂度不应该是O(n+询问*log)吗
|
kczno1 @ 2018-05-16 15:53:33
tarjan反而增加了复杂度吧。
|
gbc1749940268 @ 2019-01-29 13:29:23
这题太卡空间了吧,倍增勉强过
|