大视野在线测评-欢迎您

[ 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]