F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 5165 >> 想知道一下这题std
Rose_max @ 2018-04-09 08:48:43
[ Quote ] [ Edit ] [ Delete ] 1#
据说由于数据太水我就卡过去了。。
想知道一下std是什么
EdwardFrog @ 2018-04-09 16:42:19
[ Quote ] [ Edit ] [ Delete ] 2#
好像只要预处理不超过O(n),空间不超过O(n),单次询问不超过O(logn)都能过
没放时限的时候一个树剖日过去了
ruanxingzhi @ 2018-05-12 18:37:27
[ Quote ] [ Edit ] [ Delete ] 3#
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
[ Quote ] [ Edit ] [ Delete ] 4#
询问不超过1000次话,用O(n)-O(log)求lca,复杂度不应该是O(n+询问*log)吗
kczno1 @ 2018-05-16 15:53:33
[ Quote ] [ Edit ] [ Delete ] 5#
tarjan反而增加了复杂度吧。
gbc1749940268 @ 2019-01-29 13:29:23
[ Quote ] [ Edit ] [ Delete ] 6#
这题太卡空间了吧,倍增勉强过
[Top] [Previous Page] [Next Page]

HOME Back