这题是不是可以$O(n+m)$

YellowBean_Elsa @ 2020-02-17 20:59:07

by Marser @ 2020-02-18 09:58:57

@YellowBean tarjan求LCA不要并查集吗？

by YellowBean_Elsa @ 2020-02-18 11:21:45

好吧那应该要带一只α(n)

by 逆流之时 @ 2020-03-28 10:30:42

@YellowBean Tarjan 的并查集性质特殊，不带 log 的。可以看这篇论文。

by 逆流之时 @ 2020-03-28 10:31:19

@YellowBean 这里的 Tarjan 指的是 Tarjan 求 lca。

by YellowBean_Elsa @ 2020-03-28 17:11:15

@逆流之时 哇强啊%%%%%%%%%%%

by panyf @ 2020-12-04 08:24:59

楼上论文里的线性做法是要树分块的

一般的写法是带log的